Changeset bc216a0 in mainline


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().

Location:
uspace
Files:
1 added
32 edited

Legend:

Unmodified
Added
Removed

  • uspace/app/mkexfat/mkexfat.c

    rb17518e rbc216a0  
    4949#include <str.h>
    5050#include <getopt.h>
     51#include <macros.h>
    5152#include "exfat.h"
    5253#include "upcase.h"
    … …  
    8788#define FIRST_FREE_CLUSTER   2
    8889
    89 #define min(x, y) ((x) < (y) ? (x) : (y))
    9090
    9191typedef struct exfat_cfg {

  • uspace/app/trace/ipcp.c

    rb17518e rbc216a0  
    5353        ipc_callid_t call_hash;
    5454
    55         link_t link;
     55        ht_link_t link;
    5656} pending_call_t;
    5757
    … …  
    7373proto_t *proto_unknown;         /**< Protocol with no known methods. */
    7474
    75 static size_t pending_call_key_hash(unsigned long key[]);
    76 static size_t pending_call_hash(const link_t *item);
    77 static bool pending_call_match(unsigned long key[], size_t keys,
    78     const link_t *item);
     75
     76static size_t pending_call_key_hash(void *key)
     77{
     78        ipc_callid_t *call_id = (ipc_callid_t *)key;
     79        return *call_id;
     80}
     81
     82static size_t pending_call_hash(const ht_link_t *item)
     83{
     84        pending_call_t *hs = hash_table_get_inst(item, pending_call_t, link);
     85        return hs->call_hash;
     86}
     87
     88static bool pending_call_key_equal(void *key, const ht_link_t *item)
     89{
     90        ipc_callid_t *call_id = (ipc_callid_t *)key;
     91        pending_call_t *hs = hash_table_get_inst(item, pending_call_t, link);
     92
     93        return *call_id == hs->call_hash;
     94}
    7995
    8096static hash_table_ops_t pending_call_ops = {
    8197        .hash = pending_call_hash,
    8298        .key_hash = pending_call_key_hash,
    83         .match = pending_call_match,
     99        .key_equal = pending_call_key_equal,
    84100        .equal = 0,
    85101        .remove_callback = 0
    86102};
    87 
    88 
    89 static size_t pending_call_key_hash(unsigned long key[])
    90 {
    91         size_t hash = 17;
    92         hash = 31 * hash + key[1];
    93         hash = 31 * hash + key[0];
    94         return hash;
    95 }
    96 
    97 static size_t pending_call_hash(const link_t *item)
    98 {
    99         pending_call_t *hs = hash_table_get_instance(item, pending_call_t, link);
    100         unsigned long key[] = {
    101                 LOWER32(hs->call_hash),
    102                 UPPER32(hs->call_hash)
    103         };
    104         return pending_call_key_hash(key);
    105 }
    106 
    107 static bool pending_call_match(unsigned long key[], size_t keys,
    108         const link_t *item)
    109 {
    110         assert(keys == 2);
    111         pending_call_t *hs = hash_table_get_instance(item, pending_call_t, link);
    112 
    113         return MERGE_LOUP32(key[0], key[1]) == hs->call_hash;
    114 }
    115 
    116103
    117104
    … …  
    184171        }
    185172
    186         hash_table_create(&pending_calls, 0, 2, &pending_call_ops);
     173        bool ok = hash_table_create(&pending_calls, 0, 0, &pending_call_ops);
     174        assert(ok);
    187175}
    188176
    … …  
    338326void ipcp_call_in(ipc_call_t *call, ipc_callid_t hash)
    339327{
    340         link_t *item;
     328        ht_link_t *item;
    341329        pending_call_t *pcall;
    342330       
    … …  
    350338       
    351339        hash = hash & ~IPC_CALLID_ANSWERED;
    352         unsigned long key[] = {
    353                 LOWER32(hash),
    354                 UPPER32(hash)
    355         };
    356        
    357         item = hash_table_find(&pending_calls, key);
     340       
     341        item = hash_table_find(&pending_calls, &hash);
    358342        if (item == NULL)
    359343                return; /* No matching question found */
    … …  
    363347         */
    364348       
    365         pcall = hash_table_get_instance(item, pending_call_t, link);
    366         hash_table_remove(&pending_calls, key, 2);
     349        pcall = hash_table_get_inst(item, pending_call_t, link);
     350        hash_table_remove(&pending_calls, &hash);
    367351       
    368352        parse_answer(hash, pcall, call);

  • uspace/app/trace/proto.c

    rb17518e rbc216a0  
    4545
    4646typedef struct {
    47         unsigned srv;
     47        int srv;
    4848        proto_t *proto;
    49         link_t link;
     49        ht_link_t link;
    5050} srv_proto_t;
    5151
    5252typedef struct {
    53         sysarg_t method;
     53        int method;
    5454        oper_t *oper;
    55         link_t link;
     55        ht_link_t link;
    5656} method_oper_t;
    5757
    58 
    59 
    60 
    61 static size_t srv_proto_key_hash(unsigned long key[])
    62 {
    63         return key[0];
    64 }
    65 
    66 static size_t srv_proto_hash(const link_t *item)
    67 {
    68         srv_proto_t *sp = hash_table_get_instance(item, srv_proto_t, link);
    69         unsigned long key = sp->srv;
    70         return srv_proto_key_hash(&key);       
    71 }
    72 
    73 static bool srv_proto_match(unsigned long key[], size_t keys, const link_t *item)
    74 {
    75         srv_proto_t *sp = hash_table_get_instance(item, srv_proto_t, link);
    76 
    77         return key[0] == sp->srv;
     58/* Hash table operations. */
     59
     60static size_t srv_proto_key_hash(void *key)
     61{
     62        return *(int *)key;
     63}
     64
     65static size_t srv_proto_hash(const ht_link_t *item)
     66{
     67        srv_proto_t *sp = hash_table_get_inst(item, srv_proto_t, link);
     68        return sp->srv;
     69}
     70
     71static bool srv_proto_key_equal(void *key, const ht_link_t *item)
     72{
     73        srv_proto_t *sp = hash_table_get_inst(item, srv_proto_t, link);
     74        return sp->srv == *(int *)key;
    7875}
    7976
    … …  
    8178        .hash = srv_proto_hash,
    8279        .key_hash = srv_proto_key_hash,
    83         .match = srv_proto_match,
     80        .key_equal = srv_proto_key_equal,
    8481        .equal = 0,
    8582        .remove_callback = 0
    … …  
    8784
    8885
    89 static size_t method_oper_key_hash(unsigned long key[])
    90 {
    91         return key[0];
    92 }
    93 
    94 static size_t method_oper_hash(const link_t *item)
    95 {
    96         method_oper_t *mo = hash_table_get_instance(item, method_oper_t, link);
    97         unsigned long key = mo->method;
    98         return method_oper_key_hash(&key);
    99 }
    100 
    101 static bool method_oper_match(unsigned long key[], size_t keys,
    102         const link_t *item)
    103 {
    104         method_oper_t *mo = hash_table_get_instance(item, method_oper_t, link);
    105 
    106         return key[0] == mo->method;
     86static size_t method_oper_key_hash(void *key)
     87{
     88        return *(int *)key;
     89}
     90
     91static size_t method_oper_hash(const ht_link_t *item)
     92{
     93        method_oper_t *mo = hash_table_get_inst(item, method_oper_t, link);
     94        return mo->method;
     95}
     96
     97static bool method_oper_key_equal(void *key, const ht_link_t *item)
     98{
     99        method_oper_t *mo = hash_table_get_inst(item, method_oper_t, link);
     100        return mo->method == *(int *)key;
    107101}
    108102
    … …  
    110104        .hash = method_oper_hash,
    111105        .key_hash = method_oper_key_hash,
    112         .match = method_oper_match,
     106        .key_equal = method_oper_key_equal,
    113107        .equal = 0,
    114108        .remove_callback = 0
    … …  
    118112void proto_init(void)
    119113{
    120         hash_table_create(&srv_proto, 0, 1, &srv_proto_ops);
     114        /* todo: check return value. */
     115        bool ok = hash_table_create(&srv_proto, 0, 0, &srv_proto_ops);
     116        assert(ok);
    121117}
    122118
    … …  
    139135proto_t *proto_get_by_srv(int srv)
    140136{
    141         link_t *item;
    142         srv_proto_t *sp;
    143 
    144         unsigned long key = srv;
    145         item = hash_table_find(&srv_proto, &key);
     137        ht_link_t *item = hash_table_find(&srv_proto, &srv);
    146138        if (item == NULL) return NULL;
    147139
    148         sp = hash_table_get_instance(item, srv_proto_t, link);
     140        srv_proto_t *sp = hash_table_get_inst(item, srv_proto_t, link);
    149141        return sp->proto;
    150142}
    … …  
    153145{
    154146        proto->name = name;
    155         hash_table_create(&proto->method_oper, 0, 1, &method_oper_ops);
     147        /* todo: check return value. */
     148        bool ok = hash_table_create(&proto->method_oper, 0, 0, &method_oper_ops);
     149        assert(ok);
    156150}
    157151
    … …  
    184178oper_t *proto_get_oper(proto_t *proto, int method)
    185179{
    186         unsigned long key;
    187         link_t *item;
    188         method_oper_t *mo;
    189 
    190         key = method;
    191         item = hash_table_find(&proto->method_oper, &key);
     180        ht_link_t *item = hash_table_find(&proto->method_oper, &method);
    192181        if (item == NULL) return NULL;
    193182
    194         mo = hash_table_get_instance(item, method_oper_t, link);
     183        method_oper_t *mo = hash_table_get_inst(item, method_oper_t, link);
    195184        return mo->oper;
    196185}

  • uspace/lib/block/libblock.c

    rb17518e rbc216a0  
    254254}
    255255
    256 static size_t cache_key_hash(unsigned long *key)
    257 {
    258         /* As recommended by Effective Java, 2nd Edition. */
    259         size_t hash = 17;
    260         hash = 31 * hash + key[1];
    261         hash = 31 * hash + key[0];
    262         return hash;
    263 }
    264 
    265 static size_t cache_hash(const link_t *item)
    266 {
    267         block_t *b = hash_table_get_instance(item, block_t, hash_link);
    268         unsigned long key[] = {
    269                 LOWER32(b->lba),
    270                 UPPER32(b->lba)
    271         };
    272        
    273         return cache_key_hash(key);
    274 }
    275 
    276 static bool cache_match(unsigned long *key, size_t keys, const link_t *item)
    277 {
    278         block_t *b = hash_table_get_instance(item, block_t, hash_link);
    279         return b->lba == MERGE_LOUP32(key[0], key[1]);
     256static size_t cache_key_hash(void *key)
     257{
     258        aoff64_t *lba = (aoff64_t*)key;
     259        return *lba;
     260}
     261
     262static size_t cache_hash(const ht_link_t *item)
     263{
     264        block_t *b = hash_table_get_inst(item, block_t, hash_link);
     265        return b->lba;
     266}
     267
     268static bool cache_key_equal(void *key, const ht_link_t *item)
     269{
     270        aoff64_t *lba = (aoff64_t*)key;
     271        block_t *b = hash_table_get_inst(item, block_t, hash_link);
     272        return b->lba == *lba;
    280273}
    281274
    … …  
    284277        .hash = cache_hash,
    285278        .key_hash = cache_key_hash,
    286         .match = cache_match,
     279        .key_equal = cache_key_equal,
    287280        .equal = 0,
    288281        .remove_callback = 0
    … …  
    317310        cache->blocks_cluster = cache->lblock_size / devcon->pblock_size;
    318311
    319         if (!hash_table_create(&cache->block_hash, 0, 2, &cache_ops)) {
     312        if (!hash_table_create(&cache->block_hash, 0, 0, &cache_ops)) {
    320313                free(cache);
    321314                return ENOMEM;
    … …  
    355348                }
    356349
    357                 unsigned long key[2] = {
    358                         LOWER32(b->lba),
    359                         UPPER32(b->lba)
    360                 };
    361                 hash_table_remove(&cache->block_hash, key, 2);
     350                hash_table_remove_item(&cache->block_hash, &b->hash_link);
    362351               
    363352                free(b->data);
    … …  
    391380        fibril_rwlock_initialize(&b->contents_lock);
    392381        link_initialize(&b->free_link);
    393         link_initialize(&b->hash_link);
    394382}
    395383
    … …  
    411399        cache_t *cache;
    412400        block_t *b;
    413         link_t *l;
    414         unsigned long key[2] = {
    415                 LOWER32(ba),
    416                 UPPER32(ba)
    417         };
     401        link_t *link;
    418402
    419403        int rc;
    … …  
    431415
    432416        fibril_mutex_lock(&cache->lock);
    433         l = hash_table_find(&cache->block_hash, key);
    434         if (l) {
     417        ht_link_t *hlink = hash_table_find(&cache->block_hash, &ba);
     418        if (hlink) {
    435419found:
    436420                /*
    437421                 * We found the block in the cache.
    438422                 */
    439                 b = hash_table_get_instance(l, block_t, hash_link);
     423                b = hash_table_get_inst(hlink, block_t, hash_link);
    440424                fibril_mutex_lock(&b->lock);
    441425                if (b->refcnt++ == 0)
    … …  
    475459                                goto out;
    476460                        }
    477                         l = list_first(&cache->free_list);
    478                         b = list_get_instance(l, block_t, free_link);
     461                        link = list_first(&cache->free_list);
     462                        b = list_get_instance(link, block_t, free_link);
    479463
    480464                        fibril_mutex_lock(&b->lock);
    … …  
    516500                                        goto retry;
    517501                                }
    518                                 l = hash_table_find(&cache->block_hash, key);
    519                                 if (l) {
     502                                hlink = hash_table_find(&cache->block_hash, &ba);
     503                                if (hlink) {
    520504                                        /*
    521505                                         * Someone else must have already
    … …  
    539523                         */
    540524                        list_remove(&b->free_link);
    541                         unsigned long temp_key[2] = {
    542                                 LOWER32(b->lba),
    543                                 UPPER32(b->lba)
    544                         };
    545                         hash_table_remove(&cache->block_hash, temp_key, 2);
     525                        hash_table_remove_item(&cache->block_hash, &b->hash_link);
    546526                }
    547527
    … …  
    663643                         * Take the block out of the cache and free it.
    664644                         */
    665                         unsigned long key[2] = {
    666                                 LOWER32(block->lba),
    667                                 UPPER32(block->lba)
    668                         };
    669                         hash_table_remove(&cache->block_hash, key, 2);
     645                        hash_table_remove_item(&cache->block_hash, &block->hash_link);
    670646                        fibril_mutex_unlock(&block->lock);
    671647                        free(block->data);

  • uspace/lib/block/libblock.h

    rb17518e rbc216a0  
    8484        link_t free_link;
    8585        /** Link for placing the block into the block hash table. */
    86         link_t hash_link;
     86        ht_link_t hash_link;
    8787        /** Buffer with the block data. */
    8888        void *data;

  • uspace/lib/c/generic/adt/hash_table.c

    rb17518e rbc216a0  
    11/*
    22 * Copyright (c) 2008 Jakub Jermar
     3 * Copyright (c) 2012 Adam Hraska
     4 *
    35 * All rights reserved.
    46 *
    … …  
    6264static size_t round_up_size(size_t size);
    6365static bool alloc_table(size_t bucket_cnt, list_t **pbuckets);
    64 static void item_inserted(hash_table_t *h);
    65 static void item_removed(hash_table_t *h);
    66 static inline void remove_item(hash_table_t *h, link_t *item);
    67 static size_t remove_duplicates(hash_table_t *h, unsigned long key[]);
    68 static size_t remove_matching(hash_table_t *h, unsigned long key[], size_t key_cnt);
     66static void clear_items(hash_table_t *h);
     67static void resize(hash_table_t *h, size_t new_bucket_cnt);
     68static void grow_if_needed(hash_table_t *h);
     69static void shrink_if_needed(hash_table_t *h);
    6970
    7071/* Dummy do nothing callback to invoke in place of remove_callback == NULL. */
    71 static void nop_remove_callback(link_t *item)
     72static void nop_remove_callback(ht_link_t *item)
    7273{
    7374        /* no-op */
    … …  
    9091 *
    9192 */
    92 bool hash_table_create(hash_table_t *h, size_t init_size, size_t max_keys,
     93bool hash_table_create(hash_table_t *h, size_t init_size, size_t max_load,
    9394    hash_table_ops_t *op)
    9495{
    9596        assert(h);
    96         assert(op && op->hash && op->key_hash && op->match);
    97         assert(max_keys > 0);
     97        assert(op && op->hash && op->key_hash && op->key_equal);
     98       
     99        /* Check for compulsory ops. */
     100        if (!op || !op->hash || !op->key_hash || !op->key_equal)
     101                return false;
    98102       
    99103        h->bucket_cnt = round_up_size(init_size);
    … …  
    102106                return false;
    103107       
    104         h->max_keys = max_keys;
    105         h->items = 0;
     108        h->max_load = (max_load == 0) ? HT_MAX_LOAD : max_load;
     109        h->item_cnt = 0;
    106110        h->op = op;
    107        
    108         if (h->op->remove_callback == 0)
     111        h->full_item_cnt = h->max_load * h->bucket_cnt;
     112        h->apply_ongoing = false;
     113
     114        if (h->op->remove_callback == 0) {
    109115                h->op->remove_callback = nop_remove_callback;
     116        }
    110117       
    111118        return true;
    112119}
    113120
     121/** Destroy a hash table instance.
     122 *
     123 * @param h Hash table to be destroyed.
     124 *
     125 */
     126void hash_table_destroy(hash_table_t *h)
     127{
     128        assert(h && h->bucket);
     129        assert(!h->apply_ongoing);
     130       
     131        clear_items(h);
     132       
     133        free(h->bucket);
     134
     135        h->bucket = 0;
     136        h->bucket_cnt = 0;
     137}
     138
     139/** Returns true if there are no items in the table. */
     140bool hash_table_empty(hash_table_t *h)
     141{
     142        assert(h && h->bucket);
     143        return h->item_cnt == 0;
     144}
     145
     146/** Returns the number of items in the table. */
     147size_t hash_table_size(hash_table_t *h)
     148{
     149        assert(h && h->bucket);
     150        return h->item_cnt;
     151}
     152
    114153/** Remove all elements from the hash table
    115154 *
    … …  
    118157void hash_table_clear(hash_table_t *h)
    119158{
     159        assert(h && h->bucket);
     160        assert(!h->apply_ongoing);
     161       
     162        clear_items(h);
     163       
     164        /* Shrink the table to its minimum size if possible. */
     165        if (HT_MIN_BUCKETS < h->bucket_cnt) {
     166                resize(h, HT_MIN_BUCKETS);
     167        }
     168}
     169
     170/** Unlinks and removes all items but does not resize. */
     171static void clear_items(hash_table_t *h)
     172{
     173        if (h->item_cnt == 0)
     174                return;
     175       
    120176        for (size_t idx = 0; idx < h->bucket_cnt; ++idx) {
    121177                list_foreach_safe(h->bucket[idx], cur, next) {
     178                        assert(cur);
     179                        ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link);
     180                       
    122181                        list_remove(cur);
    123                         h->op->remove_callback(cur);
    124                 }
    125         }
    126        
    127         h->items = 0;
    128 
    129         /* Shrink the table to its minimum size if possible. */
    130         if (HT_MIN_BUCKETS < h->bucket_cnt) {
    131                 list_t *new_buckets;
    132                 if (alloc_table(HT_MIN_BUCKETS, &new_buckets)) {
    133                         free(h->bucket);
    134                         h->bucket = new_buckets;
    135                         h->bucket_cnt = HT_MIN_BUCKETS;
    136                 }
    137         }
    138 }
    139 
    140 /** Destroy a hash table instance.
    141  *
    142  * @param h Hash table to be destroyed.
    143  *
    144  */
    145 void hash_table_destroy(hash_table_t *h)
    146 {
    147         assert(h);
    148         assert(h->bucket);
    149        
    150         free(h->bucket);
    151 
    152         h->bucket = 0;
    153         h->bucket_cnt = 0;
     182                        h->op->remove_callback(cur_link);
     183                }
     184        }
     185       
     186        h->item_cnt = 0;
    154187}
    155188
    … …  
    160193 * @param item Item to be inserted into the hash table.
    161194 */
    162 void hash_table_insert(hash_table_t *h, link_t *item)
     195void hash_table_insert(hash_table_t *h, ht_link_t *item)
    163196{
    164197        assert(item);
    165198        assert(h && h->bucket);
    166         assert(h->op && h->op->hash);
     199        assert(!h->apply_ongoing);
    167200       
    168201        size_t idx = h->op->hash(item) % h->bucket_cnt;
    169202       
    170         assert(idx < h->bucket_cnt);
    171        
    172         list_append(item, &h->bucket[idx]);
    173         item_inserted(h);
     203        list_append(&item->link, &h->bucket[idx]);
     204        ++h->item_cnt;
     205        grow_if_needed(h);
    174206}
    175207
    … …  
    184216 * @return True if the inserted item was the only item with such a lookup key.
    185217 */
    186 bool hash_table_insert_unique(hash_table_t *h, link_t *item)
     218bool hash_table_insert_unique(hash_table_t *h, ht_link_t *item)
    187219{
    188220        assert(item);
    189221        assert(h && h->bucket && h->bucket_cnt);
    190222        assert(h->op && h->op->hash && h->op->equal);
    191        
    192         size_t item_hash = h->op->hash(item);
    193         size_t idx = item_hash % h->bucket_cnt;
    194        
    195         assert(idx < h->bucket_cnt);
     223        assert(!h->apply_ongoing);
     224       
     225        size_t idx = h->op->hash(item) % h->bucket_cnt;
    196226       
    197227        /* Check for duplicates. */
    … …  
    201231                 * calling equal() might very well be just as fast.
    202232                 */
    203                 if (h->op->equal(cur, item))
     233                ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link);
     234                if (h->op->equal(cur_link, item))
    204235                        return false;
    205236        }
    206237       
    207         list_append(item, &h->bucket[idx]);
    208         item_inserted(h);
     238        list_append(&item->link, &h->bucket[idx]);
     239        ++h->item_cnt;
     240        grow_if_needed(h);
    209241       
    210242        return true;
    … …  
    219251 *
    220252 */
    221 link_t *hash_table_find(const hash_table_t *h, unsigned long key[])
    222 {
    223         assert(h && h->bucket);
    224         assert(h->op && h->op->key_hash && h->op->match);
    225        
    226         size_t key_hash = h->op->key_hash(key);
    227         size_t idx = key_hash % h->bucket_cnt;
    228 
    229         assert(idx < h->bucket_cnt);
    230        
     253ht_link_t *hash_table_find(const hash_table_t *h, void *key)
     254{
     255        assert(h && h->bucket);
     256       
     257        size_t idx = h->op->key_hash(key) % h->bucket_cnt;
     258
    231259        list_foreach(h->bucket[idx], cur) {
     260                ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link);
    232261                /*
    233262                 * Is this is the item we are looking for? We could have first
    234                  * checked if the hashes match but op->match() may very well be
     263                 * checked if the hashes match but op->key_equal() may very well be
    235264                 * just as fast as op->hash().
    236265                 */
    237                 if (h->op->match(key, h->max_keys, cur)) {
    238                         return cur;
     266                if (h->op->key_equal(key, cur_link)) {
     267                        return cur_link;
    239268                }
    240269        }
    … …  
    243272}
    244273
    245 
    246 /** Apply function to all items in hash table.
    247  *
    248  * @param h   Hash table.
    249  * @param f   Function to be applied. Return false if no more items
    250  *            should be visited. The functor must not delete the successor
    251  *            of the item passed in the first argument.
    252  * @param arg Argument to be passed to the function.
    253  *
    254  */
    255 void hash_table_apply(hash_table_t *h, bool (*f)(link_t *, void *), void *arg)
    256 {       
    257         for (size_t idx = 0; idx < h->bucket_cnt; ++idx) {
    258                 list_foreach_safe(h->bucket[idx], cur, next) {
    259                         /*
    260                          * The next pointer had already been saved. f() may safely
    261                          * delete cur (but not next!).
    262                          */
    263                         if (!f(cur, arg))
    264                                 return;
    265                 }
    266         }
     274/** Find the next item equal to item. */
     275ht_link_t *hash_table_find_next(const hash_table_t *h, ht_link_t *item)
     276{
     277        assert(item);
     278        assert(h && h->bucket);
     279
     280        /* Traverse the circular list until we reach the starting item again. */
     281        for (link_t *cur = item->link.next; cur != &item->link; cur = cur->next) {
     282                assert(cur);
     283                ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link);
     284                /*
     285                 * Is this is the item we are looking for? We could have first
     286                 * checked if the hashes match but op->equal() may very well be
     287                 * just as fast as op->hash().
     288                 */
     289                if (h->op->equal(cur_link, item)) {
     290                        return cur_link;
     291                }
     292        }
     293
     294        return NULL;
    267295}
    268296
    … …  
    278306 * @return Returns the number of removed items.
    279307 */
    280 size_t hash_table_remove(hash_table_t *h, unsigned long key[], size_t key_cnt)
    281 {
    282         assert(h && h->bucket);
    283         assert(h && h->op && h->op->hash &&
    284             h->op->remove_callback);
    285         assert(key_cnt <= h->max_keys);
    286        
    287         /* All keys are known, remove from a specific bucket. */
    288         if (key_cnt == h->max_keys) {
    289                 return remove_duplicates(h, key);
    290         } else {
    291                 /*
    292                 * Fewer keys were passed.
    293                 * Any partially matching entries are to be removed.
    294                 */
    295                 return remove_matching(h, key, key_cnt);
    296         }
     308size_t hash_table_remove(hash_table_t *h, void *key)
     309{
     310        assert(h && h->bucket);
     311        assert(!h->apply_ongoing);
     312       
     313        size_t idx = h->op->key_hash(key) % h->bucket_cnt;
     314
     315        size_t removed = 0;
     316       
     317        list_foreach_safe(h->bucket[idx], cur, next) {
     318                ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link);
     319               
     320                if (h->op->key_equal(key, cur_link)) {
     321                        ++removed;
     322                        list_remove(cur);
     323                        h->op->remove_callback(cur_link);
     324                }
     325        }
     326
     327        h->item_cnt -= removed;
     328        shrink_if_needed(h);
     329       
     330        return removed;
    297331}
    298332
    299333/** Removes an item already present in the table. The item must be in the table.*/
    300 void hash_table_remove_item(hash_table_t *h, link_t *item)
     334void hash_table_remove_item(hash_table_t *h, ht_link_t *item)
    301335{
    302336        assert(item);
    303337        assert(h && h->bucket);
    304        
    305         remove_item(h, item);
    306 }
    307 
    308 /** Unlink the item from a bucket, update statistics and resize if needed. */
    309 static inline void remove_item(hash_table_t *h, link_t *item)
    310 {
    311         assert(item);
    312        
    313         list_remove(item);
    314         item_removed(h);
     338        assert(link_in_use(&item->link));
     339
     340        list_remove(&item->link);
     341        --h->item_cnt;
    315342        h->op->remove_callback(item);
    316 }
    317 
    318 /** Removes all items matching key in the bucket key hashes to. */
    319 static size_t remove_duplicates(hash_table_t *h, unsigned long key[])
    320 {
    321         assert(h && h->bucket);
    322         assert(h->op && h->op->key_hash && h->op->match);
    323        
    324         size_t key_hash = h->op->key_hash(key);
    325         size_t idx = key_hash % h->bucket_cnt;
    326 
    327         assert(idx < h->bucket_cnt);
    328        
    329         size_t removed = 0;
    330        
    331         list_foreach_safe(h->bucket[idx], cur, next) {
    332                 if (h->op->match(key, h->max_keys, cur)) {
    333                         ++removed;
    334                         remove_item(h, cur);
    335                 }
    336         }
    337        
    338         return removed;
    339 }
    340 
    341 /** Removes all items in any bucket in the table that match the partial key. */
    342 static size_t remove_matching(hash_table_t *h, unsigned long key[],
    343         size_t key_cnt)
    344 {
    345         assert(h && h->bucket);
    346         assert(key_cnt < h->max_keys);
    347        
    348         size_t removed = 0;
    349         /*
    350          * Fewer keys were passed.
    351          * Any partially matching entries are to be removed.
    352          */
     343        shrink_if_needed(h);
     344}
     345
     346/** Apply function to all items in hash table.
     347 *
     348 * @param h   Hash table.
     349 * @param f   Function to be applied. Return false if no more items
     350 *            should be visited. The functor may only delete the supplied
     351 *            item. It must not delete the successor of the item passed
     352 *            in the first argument.
     353 * @param arg Argument to be passed to the function.
     354 */
     355void hash_table_apply(hash_table_t *h, bool (*f)(ht_link_t *, void *), void *arg)
     356{       
     357        assert(f);
     358        assert(h && h->bucket);
     359       
     360        if (h->item_cnt == 0)
     361                return;
     362       
     363        h->apply_ongoing = true;
     364       
    353365        for (size_t idx = 0; idx < h->bucket_cnt; ++idx) {
    354366                list_foreach_safe(h->bucket[idx], cur, next) {
    355                         if (h->op->match(key, key_cnt, cur)) {
    356                                 ++removed;
    357                                 remove_item(h, cur);
    358                         }
    359                 }
    360         }
    361        
    362         return removed;
    363        
     367                        ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link);
     368                        /*
     369                         * The next pointer had already been saved. f() may safely
     370                         * delete cur (but not next!).
     371                         */
     372                        if (!f(cur_link, arg))
     373                                return;
     374                }
     375        }
     376       
     377        h->apply_ongoing = false;
     378       
     379        shrink_if_needed(h);
     380        grow_if_needed(h);
    364381}
    365382
    … …  
    392409}
    393410
    394 /** Allocates and rehashes items to a new table. Frees the old table. */
    395 static void resize(hash_table_t *h, size_t new_bucket_cnt)
    396 {
    397         assert(h && h->bucket);
    398        
    399         list_t *new_buckets;
    400 
    401         /* Leave the table as is if we cannot resize. */
    402         if (!alloc_table(new_bucket_cnt, &new_buckets))
    403                 return;
    404        
    405         /* Rehash all the items to the new table. */
    406         for (size_t old_idx = 0; old_idx < h->bucket_cnt; ++old_idx) {
    407                 list_foreach_safe(h->bucket[old_idx], cur, next) {
    408                         size_t new_idx = h->op->hash(cur) % new_bucket_cnt;
    409                         list_remove(cur);
    410                         list_append(cur, &new_buckets[new_idx]);
    411                 }
    412         }
    413        
    414         free(h->bucket);
    415         h->bucket = new_buckets;
    416         h->bucket_cnt = new_bucket_cnt;
    417 }
    418 
    419 /** Shrinks the table if needed. */
    420 static void item_removed(hash_table_t *h)
    421 {
    422         --h->items;
    423        
    424         if (HT_MIN_BUCKETS < h->items && h->items <= HT_MAX_LOAD * h->bucket_cnt / 4) {
     411
     412/** Shrinks the table if the table is only sparely populated. */
     413static inline void shrink_if_needed(hash_table_t *h)
     414{
     415        if (h->item_cnt <= h->full_item_cnt / 4 && HT_MIN_BUCKETS < h->bucket_cnt) {
    425416                /*
    426417                 * Keep the bucket_cnt odd (possibly also prime).
    … …  
    432423}
    433424
    434 /** Grows the table if needed. */
    435 static void item_inserted(hash_table_t *h)
    436 {
    437         ++h->items;
    438        
     425/** Grows the table if table load exceeds the maximum allowed. */
     426static inline void grow_if_needed(hash_table_t *h)
     427{
    439428        /* Grow the table if the average bucket load exceeds the maximum. */
    440         if (HT_MAX_LOAD * h->bucket_cnt < h->items) {
     429        if (h->full_item_cnt < h->item_cnt) {
    441430                /* Keep the bucket_cnt odd (possibly also prime). */
    442431                size_t new_bucket_cnt = 2 * h->bucket_cnt + 1;
    … …  
    445434}
    446435
     436/** Allocates and rehashes items to a new table. Frees the old table. */
     437static void resize(hash_table_t *h, size_t new_bucket_cnt)
     438{
     439        assert(h && h->bucket);
     440        assert(HT_MIN_BUCKETS <= new_bucket_cnt);
     441       
     442        /* We are traversing the table and resizing would mess up the buckets. */
     443        if (h->apply_ongoing)
     444                return;
     445       
     446        list_t *new_buckets;
     447
     448        /* Leave the table as is if we cannot resize. */
     449        if (!alloc_table(new_bucket_cnt, &new_buckets))
     450                return;
     451       
     452        if (0 < h->item_cnt) {
     453                /* Rehash all the items to the new table. */
     454                for (size_t old_idx = 0; old_idx < h->bucket_cnt; ++old_idx) {
     455                        list_foreach_safe(h->bucket[old_idx], cur, next) {
     456                                ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link);
     457
     458                                size_t new_idx = h->op->hash(cur_link) % new_bucket_cnt;
     459                                list_remove(cur);
     460                                list_append(cur, &new_buckets[new_idx]);
     461                        }
     462                }
     463        }
     464       
     465        free(h->bucket);
     466        h->bucket = new_buckets;
     467        h->bucket_cnt = new_bucket_cnt;
     468        h->full_item_cnt = h->max_load * h->bucket_cnt;
     469}
     470
    447471
    448472/** @}

  • uspace/lib/c/generic/async.c

    rb17518e rbc216a0  
    202202/* Client connection data */
    203203typedef struct {
    204         link_t link;
     204        ht_link_t link;
    205205       
    206206        task_id_t in_task_id;
    … …  
    214214       
    215215        /** Hash table link. */
    216         link_t link;
     216        ht_link_t link;
    217217       
    218218        /** Incoming client task ID. */
    … …  
    390390static LIST_INITIALIZE(timeout_list);
    391391
    392 static size_t client_key_hash(unsigned long key[])
    393 {
    394         assert(key);
    395         /* LOWER32(in_task_id) */
    396         return key[0] >> 4;
    397 }
    398 
    399 static size_t client_hash(const link_t *item)
    400 {
    401         client_t *client = hash_table_get_instance(item, client_t, link);
    402        
    403         unsigned long key[2] = {
    404                 LOWER32(client->in_task_id),
    405                 UPPER32(client->in_task_id),
    406         };
    407 
    408         return client_key_hash(key);
    409 }
    410 
    411 static bool client_match(unsigned long key[], size_t keys, const link_t *item)
    412 {
    413         assert(key);
    414         assert(keys == 2);
    415         assert(item);
    416        
    417         client_t *client = hash_table_get_instance(item, client_t, link);
    418         return (key[0] == LOWER32(client->in_task_id) &&
    419             (key[1] == UPPER32(client->in_task_id)));
     392static size_t client_key_hash(void *k)
     393{
     394        task_id_t key = *(task_id_t*)k;
     395        return key;
     396}
     397
     398static size_t client_hash(const ht_link_t *item)
     399{
     400        client_t *client = hash_table_get_inst(item, client_t, link);
     401        return client_key_hash(&client->in_task_id);
     402}
     403
     404static bool client_key_equal(void *k, const ht_link_t *item)
     405{
     406        task_id_t key = *(task_id_t*)k;
     407        client_t *client = hash_table_get_inst(item, client_t, link);
     408        return key == client->in_task_id;
    420409}
    421410
    … …  
    425414        .hash = client_hash,
    426415        .key_hash = client_key_hash,
    427         .match = client_match,
     416        .key_equal = client_key_equal,
    428417        .equal = 0,
    429418        .remove_callback = 0
    … …  
    437426 *
    438427 */
    439 static size_t conn_key_hash(unsigned long key[])
    440 {
    441         assert(key);
    442         return key[0] >> 4;
    443 }
    444 
    445 static size_t conn_hash(const link_t *item)
    446 {
    447         connection_t *conn = hash_table_get_instance(item, connection_t, link);
    448         unsigned long key = conn->in_phone_hash;
    449         return conn_key_hash(&key);
    450 }
    451 
    452 /** Compare hash table item with a key.
    453  *
    454  * @param key  Array containing the source phone hash as the only item.
    455  * @param keys Expected 1 but ignored.
    456  * @param item Connection hash table item.
    457  *
    458  * @return True on match, false otherwise.
    459  *
    460  */
    461 static bool conn_match(unsigned long key[], size_t keys, const link_t *item)
    462 {
    463         assert(key);
    464         assert(item);
    465        
    466         connection_t *conn = hash_table_get_instance(item, connection_t, link);
    467         return (key[0] == conn->in_phone_hash);
    468 }
    469 
    470 static bool conn_equal(const link_t *item1, const link_t *item2)
    471 {
    472         connection_t *c1 = hash_table_get_instance(item1, connection_t, link);
    473         connection_t *c2 = hash_table_get_instance(item2, connection_t, link);
    474        
    475         return c1->in_phone_hash == c2->in_phone_hash;
    476 }
    477 
    478 static void conn_remove(link_t *item)
    479 {
    480 }
     428static size_t conn_key_hash(void *key)
     429{
     430        sysarg_t in_phone_hash  = *(sysarg_t*)key;
     431        return in_phone_hash ;
     432}
     433
     434static size_t conn_hash(const ht_link_t *item)
     435{
     436        connection_t *conn = hash_table_get_inst(item, connection_t, link);
     437        return conn_key_hash(&conn->in_phone_hash);
     438}
     439
     440static bool conn_key_equal(void *key, const ht_link_t *item)
     441{
     442        sysarg_t in_phone_hash = *(sysarg_t*)key;
     443        connection_t *conn = hash_table_get_inst(item, connection_t, link);
     444        return (in_phone_hash == conn->in_phone_hash);
     445}
     446
    481447
    482448/** Operations for the connection hash table. */
    … …  
    484450        .hash = conn_hash,
    485451        .key_hash = conn_key_hash,
    486         .match = conn_match,
    487         .equal = conn_equal,
    488         .remove_callback = conn_remove
     452        .key_equal = conn_key_equal,
     453        .equal = 0,
     454        .remove_callback = 0
    489455};
    490456
    … …  
    534500        futex_down(&async_futex);
    535501       
    536         unsigned long key = call->in_phone_hash;
    537         link_t *hlp = hash_table_find(&conn_hash_table, &key);
     502        ht_link_t *hlp = hash_table_find(&conn_hash_table, &call->in_phone_hash);
    538503       
    539504        if (!hlp) {
    … …  
    542507        }
    543508       
    544         connection_t *conn = hash_table_get_instance(hlp, connection_t, link);
     509        connection_t *conn = hash_table_get_inst(hlp, connection_t, link);
    545510       
    546511        msg_t *msg = malloc(sizeof(*msg));
    … …  
    722687static client_t *async_client_get(task_id_t client_id, bool create)
    723688{
    724         unsigned long key[2] = {
    725                 LOWER32(client_id),
    726                 UPPER32(client_id),
    727         };
    728689        client_t *client = NULL;
    729690
    730691        futex_down(&async_futex);
    731         link_t *lnk = hash_table_find(&client_hash_table, key);
     692        ht_link_t *lnk = hash_table_find(&client_hash_table, &client_id);
    732693        if (lnk) {
    733                 client = hash_table_get_instance(lnk, client_t, link);
     694                client = hash_table_get_inst(lnk, client_t, link);
    734695                atomic_inc(&client->refcnt);
    735696        } else if (create) {
    … …  
    751712{
    752713        bool destroy;
    753         unsigned long key[2] = {
    754                 LOWER32(client->in_task_id),
    755                 UPPER32(client->in_task_id)
    756         };
    757        
     714
    758715        futex_down(&async_futex);
    759716       
    760717        if (atomic_predec(&client->refcnt) == 0) {
    761                 hash_table_remove(&client_hash_table, key, 2);
     718                hash_table_remove(&client_hash_table, &client->in_task_id);
    762719                destroy = true;
    763720        } else
    … …  
    855812         */
    856813        futex_down(&async_futex);
    857         unsigned long key = fibril_connection->in_phone_hash;
    858         hash_table_remove(&conn_hash_table, &key, 1);
     814        hash_table_remove(&conn_hash_table, &fibril_connection->in_phone_hash);
    859815        futex_up(&async_futex);
    860816       
    … …  
    11341090void __async_init(void)
    11351091{
    1136         if (!hash_table_create(&client_hash_table, 0, 2, &client_hash_table_ops))
     1092        if (!hash_table_create(&client_hash_table, 0, 0, &client_hash_table_ops))
    11371093                abort();
    11381094       
    1139         if (!hash_table_create(&conn_hash_table, 0, 1, &conn_hash_table_ops))
     1095        if (!hash_table_create(&conn_hash_table, 0, 0, &conn_hash_table_ops))
    11401096                abort();
    11411097       

  • uspace/lib/c/include/adt/hash_table.h

    rb17518e rbc216a0  
    11/*
    22 * Copyright (c) 2006 Jakub Jermar
     3 * Copyright (c) 2012 Adam Hraska
     4 *
    35 * All rights reserved.
    46 *
    … …  
    3941#include <unistd.h>
    4042#include <bool.h>
     43#include <macros.h>
    4144
     45/** Opaque hash table link type. */
     46typedef struct ht_link {
     47        link_t link;
     48} ht_link_t;
    4249
    4350/** Set of operations for hash table. */
    4451typedef struct {
    45         /** Returns the hash of the key stored in the item.
    46          */
    47         size_t (*hash)(const link_t *item);
     52        /** Returns the hash of the key stored in the item (ie its lookup key). */
     53        size_t (*hash)(const ht_link_t *item);
    4854       
    49         /** Returns the hash of the key.
    50          */
    51         size_t (*key_hash)(unsigned long key[]);
     55        /** Returns the hash of the key. */
     56        size_t (*key_hash)(void *key);
    5257       
    53         /** Hash table item match function.
    54          *
    55          * @param key Array of keys that will be compared with item. It is
    56          *            not necessary to pass all keys.
    57          *
    58          * @return True if the keys match, false otherwise.
    59          *
    60          */
    61         bool (*match)(unsigned long key[], size_t keys, const link_t *item);
     58        /** True if the items are equal (have the same lookup keys). */
     59        bool (*equal)(const ht_link_t *item1, const ht_link_t *item2);
    6260
    63         /**
    64          */
    65         bool (*equal)(const link_t *item1, const link_t *item2);
    66        
     61        /** Returns true if the key is equal to the item's lookup key. */
     62        bool (*key_equal)(void *key, const ht_link_t *item);
     63
    6764        /** Hash table item removal callback.
    6865         *
    … …  
    7168         * @param item Item that was removed from the hash table.
    7269         */
    73         void (*remove_callback)(link_t *item);
     70        void (*remove_callback)(ht_link_t *item);
    7471} hash_table_ops_t;
    7572
    7673/** Hash table structure. */
    7774typedef struct {
     75        hash_table_ops_t *op;
    7876        list_t *bucket;
    7977        size_t bucket_cnt;
    80         size_t max_keys;
    81         size_t items;
    82         hash_table_ops_t *op;
     78        size_t full_item_cnt;
     79        size_t item_cnt;
     80        size_t max_load;
     81        bool apply_ongoing;
    8382} hash_table_t;
    8483
    85 #define hash_table_get_instance(item, type, member) \
    86     list_get_instance((item), type, member)
     84#define hash_table_get_inst(item, type, member) \
     85        member_to_inst((item), type, member)
    8786
    8887extern bool hash_table_create(hash_table_t *, size_t, size_t,
    8988        hash_table_ops_t *);
     89extern void hash_table_destroy(hash_table_t *);
     90
     91extern bool hash_table_empty(hash_table_t *);
     92extern size_t hash_table_size(hash_table_t *);
     93
    9094extern void hash_table_clear(hash_table_t *);
    91 extern void hash_table_insert(hash_table_t *, link_t *);
    92 extern bool hash_table_insert_unique(hash_table_t *, link_t *);
    93 extern link_t *hash_table_find(const hash_table_t *, unsigned long []);
    94 extern size_t hash_table_remove(hash_table_t *, unsigned long [], size_t);
    95 extern void hash_table_remove_item(hash_table_t *, link_t *);
    96 extern void hash_table_destroy(hash_table_t *);
    97 extern void hash_table_apply(hash_table_t *, bool (*)(link_t *, void *),
     95extern void hash_table_insert(hash_table_t *, ht_link_t *);
     96extern bool hash_table_insert_unique(hash_table_t *, ht_link_t *);
     97extern ht_link_t *hash_table_find(const hash_table_t *, void *);
     98extern ht_link_t *hash_table_find_next(const hash_table_t *, ht_link_t *);
     99extern size_t hash_table_remove(hash_table_t *, void *);
     100extern void hash_table_remove_item(hash_table_t *, ht_link_t *);
     101extern void hash_table_apply(hash_table_t *, bool (*)(ht_link_t *, void *),
    98102        void *);
    99103

  • uspace/lib/c/include/adt/list.h

    rb17518e rbc216a0  
    105105        assert(((link)->prev == NULL) && ((link)->next == NULL))
    106106
     107/** Returns true if the link is definitely part of a list. False if not sure. */
     108static inline int link_in_use(link_t *link)
     109{
     110        return link->prev != NULL && link->next != NULL;
     111}
     112
    107113/** Initialize doubly-linked circular list link
    108114 *

  • uspace/lib/nic/include/nic.h

    rb17518e rbc216a0  
    4040
    4141#include <adt/list.h>
     42#include <adt/hash_table.h>
    4243#include <ddf/driver.h>
    4344#include <device/hw_res_parsed.h>
    … …  
    5354 */
    5455typedef struct nic_wol_virtue {
    55         link_t item;
     56        ht_link_t item;
    5657        nic_wv_id_t id;
    5758        nic_wv_type_t type;

  • uspace/lib/nic/src/nic_addr_db.c

    rb17518e rbc216a0  
    3636 */
    3737#include "nic_addr_db.h"
     38#include "libarch/common.h"
    3839#include <assert.h>
    3940#include <stdlib.h>
    … …  
    4344#include <adt/hash_table.h>
    4445#include <macros.h>
    45 
    46 /* The key count hash table field is not used. Use this dummy value. */
    47 #define KEY_CNT 1
    48 
    49 /**
    50  * Maximal length of addresses in the DB (in bytes).
    51  */
    52 #define NIC_ADDR_MAX_LENGTH             16
     46#include <stdint.h>
     47
    5348
    5449/**
    … …  
    5651 */
    5752typedef struct nic_addr_entry {
    58         link_t link;
    59         uint8_t addr[NIC_ADDR_MAX_LENGTH];
     53        ht_link_t link;
     54        uint8_t len;
     55        uint8_t addr[1];
    6056} nic_addr_entry_t;
    6157
    … …  
    6460 * Hash table helper functions
    6561 */
    66 
    67 static bool nic_addr_match(unsigned long *key, size_t key_cnt,
    68         const link_t *item)
    69 {
    70         uint8_t *addr = (uint8_t*)key;
    71         nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link);
    72 
    73         return 0 == bcmp(entry->addr, addr, NIC_ADDR_MAX_LENGTH);
    74 }
    75 
    76 static size_t nic_addr_key_hash(unsigned long *key)
    77 {
    78         uint8_t *addr = (uint8_t*)key;
     62typedef struct {
     63        size_t len;
     64        const uint8_t *addr;
     65} addr_key_t;
     66
     67static bool nic_addr_key_equal(void *key_arg, const ht_link_t *item)
     68{
     69        addr_key_t *key = (addr_key_t*)key_arg;
     70        nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link);
     71       
     72        return 0 == bcmp(entry->addr, key->addr, entry->len);
     73}
     74
     75static size_t addr_hash(size_t len, const uint8_t *addr)
     76{
    7977        size_t hash = 0;
    80 
    81         for (int i = NIC_ADDR_MAX_LENGTH - 1; i >= 0; --i) {
    82                 hash = (hash << 8) ^ (hash >> 24) ^ addr[i];
     78       
     79        for (size_t i = 0; i < len; ++i) {
     80                hash = (hash << 5) ^ addr[i];
    8381        }
    8482       
    … …  
    8684}
    8785
    88 static size_t nic_addr_hash(const link_t *item)
    89 {
    90         nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link);
    91        
    92         unsigned long *key = (unsigned long*)entry->addr;
    93         return nic_addr_key_hash(key);
    94 }
    95 
    96 static void nic_addr_removed(link_t *item)
     86static size_t nic_addr_key_hash(void *k)
     87{
     88        addr_key_t *key = (addr_key_t*)k;
     89        return addr_hash(key->len, key->addr);
     90}
     91
     92static size_t nic_addr_hash(const ht_link_t *item)
     93{
     94        nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link);
     95        return addr_hash(entry->len, entry->addr);
     96}
     97
     98static void nic_addr_removed(ht_link_t *item)
    9799{
    98100        nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link);
    … …  
    104106        .hash = nic_addr_hash,
    105107        .key_hash = nic_addr_key_hash,
    106         .match = nic_addr_match,
     108        .key_equal = nic_addr_key_equal,
    107109        .equal = 0,
    108110        .remove_callback = nic_addr_removed
    … …  
    122124{
    123125        assert(db);
    124         if (addr_len > NIC_ADDR_MAX_LENGTH) {
     126       
     127        if (addr_len > UCHAR_MAX)
    125128                return EINVAL;
    126         }
    127        
    128         if (!hash_table_create(&db->set, 0, KEY_CNT, &set_ops))
     129       
     130        if (!hash_table_create(&db->set, 0, 0, &set_ops))
    129131                return ENOMEM;
    130132       
    … …  
    152154{
    153155        assert(db);
    154         nic_addr_db_clear(db);
    155156        hash_table_destroy(&db->set);
    156157}
    … …  
    171172{
    172173        assert(db && addr);
    173         /* Ugly type-punning hack. */
    174         unsigned long *key = (unsigned long*)addr;
    175        
    176         if (hash_table_find(&db->set, key))
     174
     175        addr_key_t key = {
     176                .len = db->addr_len,
     177                .addr = addr
     178        };
     179       
     180        if (hash_table_find(&db->set, &key))
    177181                return EEXIST;
    178182       
    179         nic_addr_entry_t *entry = malloc(sizeof(nic_addr_entry_t));
     183        nic_addr_entry_t *entry = malloc(sizeof(nic_addr_entry_t) + db->addr_len - 1);
    180184        if (entry == NULL)
    181185                return ENOMEM;
    182        
    183         link_initialize(&entry->link);
    184        
    185         bzero(entry->addr, NIC_ADDR_MAX_LENGTH);
     186
     187        entry->len = (uint8_t) db->addr_len;
    186188        memcpy(entry->addr, addr, db->addr_len);
    187189       
    … …  
    202204{
    203205        assert(db && addr);
    204         unsigned long *key = (unsigned long*)addr;
    205        
    206         link_t *item = hash_table_find(&db->set, key);
    207        
    208         if (item) {
    209                 hash_table_remove_item(&db->set, item);
     206       
     207        addr_key_t key = {
     208                .len = db->addr_len,
     209                .addr = addr
     210        };
     211       
     212        if (hash_table_remove(&db->set, &key))
    210213                return EOK;
    211         } else {
     214        else
    212215                return ENOENT;
    213         }
    214216}
    215217
    … …  
    225227{
    226228        assert(db && addr);
    227         unsigned long *key = (unsigned long*)addr;
    228        
    229         return 0 != hash_table_find(&db->set, key);
     229       
     230        addr_key_t key = {
     231                .len = db->addr_len,
     232                .addr = addr
     233        };
     234       
     235        return 0 != hash_table_find(&db->set, &key);
    230236}
    231237
    … …  
    241247 * Helper function for nic_addr_db_foreach
    242248 */
    243 static bool nic_addr_db_fe_helper(link_t *item, void *arg)
     249static bool nic_addr_db_fe_helper(ht_link_t *item, void *arg)
    244250{
    245251        nic_addr_db_fe_arg_t *hs = (nic_addr_db_fe_arg_t *) arg;

  • uspace/lib/nic/src/nic_wol_virtues.c

    rb17518e rbc216a0  
    3737
    3838#include "nic_wol_virtues.h"
     39#include "nic.h"
    3940#include <assert.h>
    4041#include <errno.h>
    … …  
    4546 */
    4647
    47 static size_t nic_wv_key_hash(unsigned long keys[])
    48 {
    49         return keys[0];
    50 }
    51 
    52 static size_t nic_wv_hash(const link_t *item)
     48static size_t nic_wv_key_hash(void *key)
     49{
     50        return *(nic_wv_id_t*) key;
     51}
     52
     53static size_t nic_wv_hash(const ht_link_t *item)
    5354{
    5455        nic_wol_virtue_t *virtue = (nic_wol_virtue_t *) item;
    55         unsigned long key = virtue->id;
    56         return nic_wv_key_hash(&key);
    57 }
    58 
    59 static bool nic_wv_match(unsigned long key[], size_t keys, const link_t *item)
     56        return virtue->id;
     57}
     58
     59static bool nic_wv_key_equal(void *key, const ht_link_t *item)
    6060{
    6161        nic_wol_virtue_t *virtue = (nic_wol_virtue_t *) item;
    62         return (virtue->id == (nic_wv_id_t) key[0]);
     62        return (virtue->id == *(nic_wv_id_t*) key);
    6363}
    6464
    … …  
    7676        wvs->table_operations.hash = nic_wv_hash;
    7777        wvs->table_operations.key_hash = nic_wv_key_hash;
    78         wvs->table_operations.match = nic_wv_match;
     78        wvs->table_operations.key_equal = nic_wv_key_equal;
    7979        wvs->table_operations.equal = 0;
    8080        wvs->table_operations.remove_callback = 0;
    8181       
    82         if (!hash_table_create(&wvs->table, 0, 1, &wvs->table_operations)) {
     82        if (!hash_table_create(&wvs->table, 0, 0, &wvs->table_operations)) {
    8383                return ENOMEM;
    8484        }
    … …  
    168168        do {
    169169                virtue->id = wvs->next_id++;
    170         } while (NULL !=
    171                 hash_table_find(&wvs->table, (unsigned long *) &virtue->id));
     170        } while (NULL != hash_table_find(&wvs->table, &virtue->id));
    172171        hash_table_insert(&wvs->table, &virtue->item);
    173172        virtue->next = wvs->lists[virtue->type];
    … …  
    188187nic_wol_virtue_t *nic_wol_virtues_remove(nic_wol_virtues_t *wvs, nic_wv_id_t id)
    189188{
    190         nic_wol_virtue_t *virtue = (nic_wol_virtue_t *)
    191                 hash_table_find(&wvs->table, (unsigned long *) &id);
     189        nic_wol_virtue_t *virtue =
     190                (nic_wol_virtue_t *) hash_table_find(&wvs->table, &id);
    192191        if (virtue == NULL) {
    193192                return NULL;
    … …  
    195194
    196195        /* Remove from filter_table */
    197         hash_table_remove(&wvs->table, (unsigned long *) &id, 1);
     196        hash_table_remove_item(&wvs->table, &virtue->item);
    198197
    199198        /* Remove from filter_types */
    … …  
    232231         * constant virtue the retyping is correct.
    233232         */
    234         link_t *virtue = hash_table_find(
    235                 &((nic_wol_virtues_t *) wvs)->table, (unsigned long *) &id);
     233        ht_link_t *virtue = hash_table_find(&((nic_wol_virtues_t *) wvs)->table, &id);
    236234        return (const nic_wol_virtue_t *) virtue;
    237235}

  • uspace/srv/devman/devman.c

    rb17518e rbc216a0  
    6666/* hash table operations */
    6767
    68 static size_t devices_key_hash(unsigned long key[])
    69 {
    70         return key[0];
    71 }
    72 
    73 static size_t devman_devices_hash(const link_t *item)
    74 {
    75         dev_node_t *dev = hash_table_get_instance(item, dev_node_t, devman_dev);
    76         unsigned long key = dev->handle;
    77         return devices_key_hash(&key);
    78 }
    79 
    80 static size_t devman_functions_hash(const link_t *item)
    81 {
    82         fun_node_t *fun = hash_table_get_instance(item, fun_node_t, devman_fun);
    83         unsigned long key = fun->handle;
    84         return devices_key_hash(&key);
    85 }
    86 
    87 static size_t loc_functions_hash(const link_t *item)
    88 {
    89         fun_node_t *fun = hash_table_get_instance(item, fun_node_t, loc_fun);
    90         unsigned long key = fun->service_id;
    91         return devices_key_hash(&key);
    92 }
    93 
    94 static bool devman_devices_match(unsigned long key[], size_t keys,
    95     const link_t *item)
    96 {
    97         dev_node_t *dev = hash_table_get_instance(item, dev_node_t, devman_dev);
    98         return (dev->handle == (devman_handle_t) key[0]);
    99 }
    100 
    101 static bool devman_functions_match(unsigned long key[], size_t keys,
    102     const link_t *item)
    103 {
    104         fun_node_t *fun = hash_table_get_instance(item, fun_node_t, devman_fun);
    105         return (fun->handle == (devman_handle_t) key[0]);
    106 }
    107 
    108 static bool loc_functions_match(unsigned long key[], size_t keys,
    109     const link_t *item)
    110 {
    111         fun_node_t *fun = hash_table_get_instance(item, fun_node_t, loc_fun);
    112         return (fun->service_id == (service_id_t) key[0]);
     68static inline size_t handle_key_hash(void *key)
     69{
     70        devman_handle_t handle = *(devman_handle_t*)key;
     71        return handle;
     72}
     73
     74static size_t devman_devices_hash(const ht_link_t *item)
     75{
     76        dev_node_t *dev = hash_table_get_inst(item, dev_node_t, devman_dev);
     77        return handle_key_hash(&dev->handle);
     78}
     79
     80static size_t devman_functions_hash(const ht_link_t *item)
     81{
     82        fun_node_t *fun = hash_table_get_inst(item, fun_node_t, devman_fun);
     83        return handle_key_hash(&fun->handle);
     84}
     85
     86static bool devman_devices_key_equal(void *key, const ht_link_t *item)
     87{
     88        devman_handle_t handle = *(devman_handle_t*)key;
     89        dev_node_t *dev = hash_table_get_inst(item, dev_node_t, devman_dev);
     90        return dev->handle == handle;
     91}
     92
     93static bool devman_functions_key_equal(void *key, const ht_link_t *item)
     94{
     95        devman_handle_t handle = *(devman_handle_t*)key;
     96        fun_node_t *fun = hash_table_get_inst(item, fun_node_t, devman_fun);
     97        return fun->handle == handle;
     98}
     99
     100static inline size_t service_id_key_hash(void *key)
     101{
     102        service_id_t service_id = *(service_id_t*)key;
     103        return service_id;
     104}
     105
     106static size_t loc_functions_hash(const ht_link_t *item)
     107{
     108        fun_node_t *fun = hash_table_get_inst(item, fun_node_t, loc_fun);
     109        return service_id_key_hash(&fun->service_id);
     110}
     111
     112static bool loc_functions_key_equal(void *key, const ht_link_t *item)
     113{
     114        service_id_t service_id = *(service_id_t*)key;
     115        fun_node_t *fun = hash_table_get_inst(item, fun_node_t, loc_fun);
     116        return fun->service_id == service_id;
    113117}
    114118
    … …  
    116120static hash_table_ops_t devman_devices_ops = {
    117121        .hash = devman_devices_hash,
    118         .key_hash = devices_key_hash,
    119         .match = devman_devices_match,
     122        .key_hash = handle_key_hash,
     123        .key_equal = devman_devices_key_equal,
    120124        .equal = 0,
    121125        .remove_callback = 0
    … …  
    124128static hash_table_ops_t devman_functions_ops = {
    125129        .hash = devman_functions_hash,
    126         .key_hash = devices_key_hash,
    127         .match = devman_functions_match,
     130        .key_hash = handle_key_hash,
     131        .key_equal = devman_functions_key_equal,
    128132        .equal = 0,
    129133        .remove_callback = 0
    … …  
    132136static hash_table_ops_t loc_devices_ops = {
    133137        .hash = loc_functions_hash,
    134         .key_hash = devices_key_hash,
    135         .match = loc_functions_match,
     138        .key_hash = service_id_key_hash,
     139        .key_equal = loc_functions_key_equal,
    136140        .equal = 0,
    137141        .remove_callback = 0
    … …  
    9981002        tree->current_handle = 0;
    9991003       
    1000         hash_table_create(&tree->devman_devices, 0, 1, &devman_devices_ops);
    1001         hash_table_create(&tree->devman_functions, 0, 1, &devman_functions_ops);
    1002         hash_table_create(&tree->loc_functions, 0, 1, &loc_devices_ops);
     1004        hash_table_create(&tree->devman_devices, 0, 0, &devman_devices_ops);
     1005        hash_table_create(&tree->devman_functions, 0, 0, &devman_functions_ops);
     1006        hash_table_create(&tree->loc_functions, 0, 0, &loc_devices_ops);
    10031007       
    10041008        fibril_rwlock_initialize(&tree->rwlock);
    … …  
    10341038        list_initialize(&dev->functions);
    10351039        link_initialize(&dev->driver_devices);
    1036         link_initialize(&dev->devman_dev);
    10371040       
    10381041        return dev;
    … …  
    10821085dev_node_t *find_dev_node_no_lock(dev_tree_t *tree, devman_handle_t handle)
    10831086{
    1084         unsigned long key = handle;
    1085         link_t *link;
    1086        
    10871087        assert(fibril_rwlock_is_locked(&tree->rwlock));
    10881088       
    1089         link = hash_table_find(&tree->devman_devices, &key);
     1089        ht_link_t *link = hash_table_find(&tree->devman_devices, &handle);
    10901090        if (link == NULL)
    10911091                return NULL;
    10921092       
    1093         return hash_table_get_instance(link, dev_node_t, devman_dev);
     1093        return hash_table_get_inst(link, dev_node_t, devman_dev);
    10941094}
    10951095
    … …  
    11651165        link_initialize(&fun->dev_functions);
    11661166        list_initialize(&fun->match_ids.ids);
    1167         link_initialize(&fun->devman_fun);
    1168         link_initialize(&fun->loc_fun);
    11691167       
    11701168        return fun;
    … …  
    12151213fun_node_t *find_fun_node_no_lock(dev_tree_t *tree, devman_handle_t handle)
    12161214{
    1217         unsigned long key = handle;
    1218         link_t *link;
    12191215        fun_node_t *fun;
    12201216       
    12211217        assert(fibril_rwlock_is_locked(&tree->rwlock));
    12221218       
    1223         link = hash_table_find(&tree->devman_functions, &key);
     1219        ht_link_t *link = hash_table_find(&tree->devman_functions, &handle);
    12241220        if (link == NULL)
    12251221                return NULL;
    12261222       
    1227         fun = hash_table_get_instance(link, fun_node_t, devman_fun);
     1223        fun = hash_table_get_inst(link, fun_node_t, devman_fun);
    12281224       
    12291225        return fun;
    … …  
    13241320       
    13251321        /* Remove node from the handle-to-node map. */
    1326         unsigned long key = dev->handle;
    1327         hash_table_remove(&tree->devman_devices, &key, 1);
     1322        hash_table_remove(&tree->devman_devices, &dev->handle);
    13281323       
    13291324        /* Unlink from parent function. */
    … …  
    13861381       
    13871382        /* Remove the node from the handle-to-node map. */
    1388         unsigned long key = fun->handle;
    1389         hash_table_remove(&tree->devman_functions, &key, 1);
     1383        hash_table_remove(&tree->devman_functions, &fun->handle);
    13901384       
    13911385        /* Remove the node from the list of its parent's children. */
    … …  
    15001494{
    15011495        fun_node_t *fun = NULL;
    1502         link_t *link;
    1503         unsigned long key = (unsigned long) service_id;
    15041496       
    15051497        fibril_rwlock_read_lock(&tree->rwlock);
    1506         link = hash_table_find(&tree->loc_functions, &key);
     1498        ht_link_t *link = hash_table_find(&tree->loc_functions, &service_id);
    15071499        if (link != NULL) {
    1508                 fun = hash_table_get_instance(link, fun_node_t, loc_fun);
     1500                fun = hash_table_get_inst(link, fun_node_t, loc_fun);
    15091501                fun_add_ref(fun);
    15101502        }

  • uspace/srv/devman/devman.h

    rb17518e rbc216a0  
    150150         * Used by the hash table of devices indexed by devman device handles.
    151151         */
    152         link_t devman_dev;
     152        ht_link_t devman_dev;
    153153       
    154154        /**
    … …  
    201201         * Used by the hash table of functions indexed by devman device handles.
    202202         */
    203         link_t devman_fun;
     203        ht_link_t devman_fun;
    204204       
    205205        /**
    206206         * Used by the hash table of functions indexed by service IDs.
    207207         */
    208         link_t loc_fun;
     208        ht_link_t loc_fun;
    209209};
    210210

  • uspace/srv/fs/cdfs/cdfs_ops.c

    rb17518e rbc216a0  
    3737 */
    3838
     39#include "cdfs_ops.h"
    3940#include <bool.h>
    4041#include <adt/hash_table.h>
     42#include <adt/hash.h>
    4143#include <malloc.h>
    4244#include <mem.h>
    … …  
    5052#include "cdfs.h"
    5153#include "cdfs_endian.h"
    52 #include "cdfs_ops.h"
    5354
    5455/** Standard CD-ROM block size */
    5556#define BLOCK_SIZE  2048
    5657
    57 /** Implicit node cache size
    58  *
    59  * More nodes can be actually cached if the files remain
    60  * opended.
    61  *
    62  */
    63 #define NODE_CACHE_SIZE  200
    64 
    65 #define NODES_KEY_SRVC   0
    66 #define NODES_KEY_INDEX  1
     58#define NODE_CACHE_SIZE 200
    6759
    6860/** All root nodes have index 0 */
    … …  
    203195        service_id_t service_id;  /**< Service ID of block device */
    204196       
    205         link_t nh_link;           /**< Nodes hash table link */
     197        ht_link_t nh_link;        /**< Nodes hash table link */
    206198        cdfs_dentry_type_t type;  /**< Dentry type */
    207199       
    … …  
    224216static hash_table_t nodes;
    225217
    226 static size_t nodes_key_hash(unsigned long key[])
    227 {
    228         return key[NODES_KEY_INDEX];
    229 }
    230 
    231 static size_t nodes_hash(const link_t *item)
    232 {
    233         cdfs_node_t *node = hash_table_get_instance(item, cdfs_node_t, nh_link);
    234        
    235         unsigned long key[] = {
    236                 [NODES_KEY_INDEX] = node->index
    237         };
    238        
    239         return nodes_key_hash(key);
    240 }
    241 
    242 static bool nodes_match(unsigned long key[], size_t keys, const link_t *item)
    243 {
    244         cdfs_node_t *node = hash_table_get_instance(item, cdfs_node_t, nh_link);
    245        
    246         if (keys == 1) {
    247                 return (node->service_id == key[NODES_KEY_SRVC]);
    248         } else {
    249                 assert(keys == 2);
    250                 return ((node->service_id == key[NODES_KEY_SRVC]) &&
    251                     (node->index == key[NODES_KEY_INDEX]));
    252         }
    253 }
    254 
    255 static bool nodes_equal(const link_t *item1, const link_t *item2)
    256 {
    257         cdfs_node_t *node1 = hash_table_get_instance(item1, cdfs_node_t, nh_link);
    258         cdfs_node_t *node2 = hash_table_get_instance(item2, cdfs_node_t, nh_link);
    259        
    260         return node1->service_id == node2->service_id
    261                 && node1->index == node2->index;
    262 }
    263 
    264 static void nodes_remove_callback(link_t *item)
    265 {
    266         cdfs_node_t *node = hash_table_get_instance(item, cdfs_node_t, nh_link);
     218/*
     219 * Hash table support functions.
     220 */
     221
     222typedef struct {
     223        service_id_t service_id;
     224    fs_index_t index;
     225} ht_key_t;
     226
     227static size_t nodes_key_hash(void *k)
     228{
     229        ht_key_t *key = (ht_key_t*)k;
     230        return hash_combine(key->service_id, key->index);
     231}
     232
     233static size_t nodes_hash(const ht_link_t *item)
     234{
     235        cdfs_node_t *node = hash_table_get_inst(item, cdfs_node_t, nh_link);
     236        return hash_combine(node->service_id, node->index);
     237}
     238
     239static bool nodes_key_equal(void *k, const ht_link_t *item)
     240{
     241        cdfs_node_t *node = hash_table_get_inst(item, cdfs_node_t, nh_link);
     242        ht_key_t *key = (ht_key_t*)k;
     243       
     244        return key->service_id == node->service_id && key->index == node->index;
     245}
     246
     247static void nodes_remove_callback(ht_link_t *item)
     248{
     249        cdfs_node_t *node = hash_table_get_inst(item, cdfs_node_t, nh_link);
    267250       
    268251        assert(node->type == CDFS_DIRECTORY);
    … …  
    283266        .hash = nodes_hash,
    284267        .key_hash = nodes_key_hash,
    285         .match = nodes_match,
    286         .equal = nodes_equal,
     268        .key_equal = nodes_key_equal,
     269        .equal = 0,
    287270        .remove_callback = nodes_remove_callback
    288271};
    … …  
    291274    fs_index_t index)
    292275{
    293         unsigned long key[] = {
    294                 [NODES_KEY_SRVC] = service_id,
    295                 [NODES_KEY_INDEX] = index
     276        ht_key_t key = {
     277                .index = index,
     278                .service_id = service_id
    296279        };
    297280       
    298         link_t *link = hash_table_find(&nodes, key);
     281        ht_link_t *link = hash_table_find(&nodes, &key);
    299282        if (link) {
    300283                cdfs_node_t *node =
    301                     hash_table_get_instance(link, cdfs_node_t, nh_link);
     284                    hash_table_get_inst(link, cdfs_node_t, nh_link);
    302285               
    303286                *rfn = FS_NODE(node);
    … …  
    325308        node->opened = 0;
    326309       
    327         link_initialize(&node->nh_link);
    328310        list_initialize(&node->cs_list);
    329311}
    … …  
    517499static fs_node_t *get_cached_node(service_id_t service_id, fs_index_t index)
    518500{
    519         unsigned long key[] = {
    520                 [NODES_KEY_SRVC] = service_id,
    521                 [NODES_KEY_INDEX] = index
     501        ht_key_t key = {
     502                .index = index,
     503                .service_id = service_id
    522504        };
    523505       
    524         link_t *link = hash_table_find(&nodes, key);
     506        ht_link_t *link = hash_table_find(&nodes, &key);
    525507        if (link) {
    526508                cdfs_node_t *node =
    527                     hash_table_get_instance(link, cdfs_node_t, nh_link);
     509                    hash_table_get_inst(link, cdfs_node_t, nh_link);
    528510                return FS_NODE(node);
    529511        }
    … …  
    811793}
    812794
     795static bool rm_service_id_nodes(ht_link_t *item, void *arg)
     796{
     797        service_id_t service_id = *(service_id_t*)arg;
     798        cdfs_node_t *node = hash_table_get_inst(item, cdfs_node_t, nh_link);
     799       
     800        if (node->service_id == service_id) {
     801                hash_table_remove_item(&nodes, &node->nh_link);
     802        }
     803       
     804        return true;
     805}
     806
    813807static void cdfs_instance_done(service_id_t service_id)
    814808{
    815         unsigned long key[] = {
    816                 [NODES_KEY_SRVC] = service_id
    817         };
    818        
    819         hash_table_remove(&nodes, key, 1);
     809        hash_table_apply(&nodes, rm_service_id_nodes, &service_id);
    820810        block_cache_fini(service_id);
    821811        block_fini(service_id);
    … …  
    831821    size_t *rbytes)
    832822{
    833         unsigned long key[] = {
    834                 [NODES_KEY_SRVC] = service_id,
    835                 [NODES_KEY_INDEX] = index
     823        ht_key_t key = {
     824                .index = index,
     825                .service_id = service_id
    836826        };
    837827       
    838         link_t *link = hash_table_find(&nodes, key);
     828        ht_link_t *link = hash_table_find(&nodes, &key);
    839829        if (link == NULL)
    840830                return ENOENT;
    841831       
    842832        cdfs_node_t *node =
    843             hash_table_get_instance(link, cdfs_node_t, nh_link);
     833            hash_table_get_inst(link, cdfs_node_t, nh_link);
    844834       
    845835        if (!node->processed) {
    … …  
    921911}
    922912
    923 static bool cache_remove_closed(link_t *item, void *arg)
     913static bool cache_remove_closed(ht_link_t *item, void *arg)
    924914{
    925915        size_t *premove_cnt = (size_t*)arg;
    … …  
    927917        /* Some nodes were requested to be removed from the cache. */
    928918        if (0 < *premove_cnt) {
    929                 cdfs_node_t *node =     hash_table_get_instance(item, cdfs_node_t, nh_link);
     919                cdfs_node_t *node =     hash_table_get_inst(item, cdfs_node_t, nh_link);
    930920
    931921                if (!node->opened) {
    … …  
    957947                return EOK;
    958948       
    959         unsigned long key[] = {
    960                 [NODES_KEY_SRVC] = service_id,
    961                 [NODES_KEY_INDEX] = index
     949        ht_key_t key = {
     950                .index = index,
     951                .service_id = service_id
    962952        };
    963953       
    964         link_t *link = hash_table_find(&nodes, key);
     954        ht_link_t *link = hash_table_find(&nodes, &key);
    965955        if (link == 0)
    966956                return ENOENT;
    967957       
    968958        cdfs_node_t *node =
    969             hash_table_get_instance(link, cdfs_node_t, nh_link);
     959            hash_table_get_inst(link, cdfs_node_t, nh_link);
    970960       
    971961        assert(node->opened > 0);
    … …  
    10131003bool cdfs_init(void)
    10141004{
    1015         if (!hash_table_create(&nodes, 0, 2, &nodes_ops))
     1005        if (!hash_table_create(&nodes, 0, 0, &nodes_ops))
    10161006                return false;
    10171007       

  • uspace/srv/fs/exfat/exfat.h

    rb17518e rbc216a0  
    106106typedef struct {
    107107        /** Used indices (position) hash table link. */
    108         link_t          uph_link;
     108        ht_link_t               uph_link;
    109109        /** Used indices (index) hash table link. */
    110         link_t          uih_link;
     110        ht_link_t               uih_link;
    111111
    112112        fibril_mutex_t  lock;

  • 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

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

    rb17518e rbc216a0  
    5454#include <byteorder.h>
    5555#include <adt/hash_table.h>
     56#include <adt/hash.h>
    5657#include <adt/list.h>
    5758#include <assert.h>

  • uspace/srv/fs/ext2fs/ext2fs_ops.c

    rb17518e rbc216a0  
    4949#include <byteorder.h>
    5050#include <adt/hash_table.h>
     51#include <adt/hash.h>
    5152#include <adt/list.h>
    5253#include <assert.h>
    … …  
    6263#define EXT2FS_NODE(node)       ((node) ? (ext2fs_node_t *) (node)->data : NULL)
    6364#define EXT2FS_DBG(format, ...) {if (false) printf("ext2fs: %s: " format "\n", __FUNCTION__, ##__VA_ARGS__);}
    64 #define OPEN_NODES_KEYS 2
    65 #define OPEN_NODES_DEV_HANDLE_KEY 0
    66 #define OPEN_NODES_INODE_KEY 1
    6765
    6866typedef struct ext2fs_instance {
    … …  
    7775        ext2_inode_ref_t *inode_ref;
    7876        fs_node_t *fs_node;
    79         link_t link;
     77        ht_link_t link;
    8078        unsigned int references;
    8179} ext2fs_node_t;
    … …  
    121119static FIBRIL_MUTEX_INITIALIZE(open_nodes_lock);
    122120
    123 /* Hash table interface for open nodes hash table */
    124 static size_t open_nodes_key_hash(unsigned long key[])
    125 {
    126         /* Hash construction recommended in Effective Java, 2nd Edition. */
    127         size_t hash = 17;
    128         hash = 31 * hash + key[OPEN_NODES_DEV_HANDLE_KEY];
    129         hash = 31 * hash + key[OPEN_NODES_INODE_KEY];
    130         return hash;
    131 }
    132 
    133 static size_t open_nodes_hash(const link_t *item)
    134 {
    135         ext2fs_node_t *enode = hash_table_get_instance(item, ext2fs_node_t, link);
     121/*
     122 * Hash table interface for open nodes hash table
     123 */
     124
     125typedef struct {
     126        service_id_t service_id;
     127        fs_index_t index;
     128} node_key_t;
     129
     130static size_t open_nodes_key_hash(void *key)
     131{
     132        node_key_t *node_key = (node_key_t*)key;
     133        return hash_combine(node_key->service_id, node_key->index);
     134}
     135
     136static size_t open_nodes_hash(const ht_link_t *item)
     137{
     138        ext2fs_node_t *enode = hash_table_get_inst(item, ext2fs_node_t, link);
    136139
    137140        assert(enode->instance);
    138141        assert(enode->inode_ref);
    139142       
    140         unsigned long key[] = {
    141                 [OPEN_NODES_DEV_HANDLE_KEY] = enode->instance->service_id,
    142                 [OPEN_NODES_INODE_KEY] = enode->inode_ref->index,
    143         };
    144        
    145         return open_nodes_key_hash(key);
    146 }
    147 
    148 static bool open_nodes_match(unsigned long key[], size_t keys,
    149     const link_t *item)
    150 {
    151         ext2fs_node_t *enode = hash_table_get_instance(item, ext2fs_node_t, link);
    152         assert(keys > 0);
    153         if (enode->instance->service_id !=
    154             ((service_id_t) key[OPEN_NODES_DEV_HANDLE_KEY])) {
    155                 return false;
    156         }
    157         if (keys == 1) {
    158                 return true;
    159         }
    160         assert(keys == 2);
    161         return (enode->inode_ref->index == key[OPEN_NODES_INODE_KEY]);
     143        return hash_combine(enode->instance->service_id, enode->inode_ref->index);
     144}
     145
     146static bool open_nodes_key_equal(void *key, const ht_link_t *item)
     147{
     148        node_key_t *node_key = (node_key_t*)key;
     149        ext2fs_node_t *enode = hash_table_get_inst(item, ext2fs_node_t, link);
     150       
     151        return node_key->service_id == enode->instance->service_id
     152                && node_key->index == enode->inode_ref->index;
    162153}
    163154
    … …  
    165156        .hash = open_nodes_hash,
    166157        .key_hash = open_nodes_key_hash,
    167         .match = open_nodes_match,
     158        .key_equal = open_nodes_key_equal,
    168159        .equal = 0,
    169160        .remove_callback = 0,
    … …  
    175166int ext2fs_global_init(void)
    176167{
    177         if (!hash_table_create(&open_nodes, 0, OPEN_NODES_KEYS, &open_nodes_ops)) {
     168        if (!hash_table_create(&open_nodes, 0, 0, &open_nodes_ops)) {
    178169                return ENOMEM;
    179170        }
    … …  
    329320       
    330321        /* Check if the node is not already open */
    331         unsigned long key[] = {
    332                 [OPEN_NODES_DEV_HANDLE_KEY] = inst->service_id,
    333                 [OPEN_NODES_INODE_KEY] = index,
     322        node_key_t key = {
     323                .service_id = inst->service_id,
     324                .index = index
    334325        };
    335         link_t *already_open = hash_table_find(&open_nodes, key);
     326        ht_link_t *already_open = hash_table_find(&open_nodes, &key);
    336327
    337328        if (already_open) {
    338                 enode = hash_table_get_instance(already_open, ext2fs_node_t, link);
     329                enode = hash_table_get_inst(already_open, ext2fs_node_t, link);
    339330                *rfn = enode->fs_node;
    340331                enode->references++;
    … …  
    370361        enode->references = 1;
    371362        enode->fs_node = node;
    372         link_initialize(&enode->link);
    373363       
    374364        node->data = enode;
    … …  
    421411int ext2fs_node_put_core(ext2fs_node_t *enode)
    422412{
    423         int rc;
    424 
    425         unsigned long key[] = {
    426                 [OPEN_NODES_DEV_HANDLE_KEY] = enode->instance->service_id,
    427                 [OPEN_NODES_INODE_KEY] = enode->inode_ref->index,
     413        node_key_t key = {
     414                .service_id = enode->instance->service_id,
     415                .index = enode->inode_ref->index
    428416        };
    429         hash_table_remove(&open_nodes, key, OPEN_NODES_KEYS);
     417
     418        hash_table_remove(&open_nodes, &key);
     419       
    430420        assert(enode->instance->open_nodes_count > 0);
    431421        enode->instance->open_nodes_count--;
    432422
    433         rc = ext2_filesystem_put_inode_ref(enode->inode_ref);
     423        int rc = ext2_filesystem_put_inode_ref(enode->inode_ref);
    434424        if (rc != EOK) {
    435425                EXT2FS_DBG("ext2_filesystem_put_inode_ref failed");

  • uspace/srv/fs/fat/fat.h

    rb17518e rbc216a0  
    190190typedef struct {
    191191        /** Used indices (position) hash table link. */
    192         link_t          uph_link;
     192        ht_link_t               uph_link;
    193193        /** Used indices (index) hash table link. */
    194         link_t          uih_link;
     194        ht_link_t               uih_link;
    195195
    196196        fibril_mutex_t  lock;

  • 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

  • uspace/srv/fs/locfs/locfs_ops.c

    rb17518e rbc216a0  
    6161        async_sess_t *sess;       /**< If NULL, the structure is incomplete. */
    6262        size_t refcount;
    63         link_t link;
     63        ht_link_t link;
    6464        fibril_condvar_t cv;      /**< Broadcast when completed. */
    6565} service_t;
    … …  
    7171static FIBRIL_MUTEX_INITIALIZE(services_mutex);
    7272
    73 #define SERVICES_KEYS        1
    74 #define SERVICES_KEY_HANDLE  0
    75 
    7673/* Implementation of hash table interface for the nodes hash table. */
    7774
    78 static size_t services_key_hash(unsigned long key[])
    79 {
    80         return key[SERVICES_KEY_HANDLE];
    81 }
    82 
    83 static size_t services_hash(const link_t *item)
    84 {
    85         service_t *dev = hash_table_get_instance(item, service_t, link);
    86         unsigned long key[] = {
    87                 [SERVICES_KEY_HANDLE] = dev->service_id
    88         };
    89        
    90         return services_key_hash(key);
    91 }
    92 
    93 static bool services_match(unsigned long key[], size_t keys, const link_t *item)
    94 {
    95         assert(keys == 1);
    96         service_t *dev = hash_table_get_instance(item, service_t, link);
    97         return (dev->service_id == (service_id_t) key[SERVICES_KEY_HANDLE]);
    98 }
    99 
    100 static void services_remove_callback(link_t *item)
    101 {
    102         free(hash_table_get_instance(item, service_t, link));
     75static size_t services_key_hash(void *key)
     76{
     77        return *(service_id_t*)key;
     78}
     79
     80static size_t services_hash(const ht_link_t *item)
     81{
     82        service_t *dev = hash_table_get_inst(item, service_t, link);
     83        return dev->service_id;
     84}
     85
     86static bool services_key_equal(void *key, const ht_link_t *item)
     87{
     88        service_t *dev = hash_table_get_inst(item, service_t, link);
     89        return (dev->service_id == *(service_id_t*)key);
     90}
     91
     92static void services_remove_callback(ht_link_t *item)
     93{
     94        free(hash_table_get_inst(item, service_t, link));
    10395}
    10496
    … …  
    10698        .hash = services_hash,
    10799        .key_hash = services_key_hash,
    108         .match = services_match,
     100        .key_equal = services_key_equal,
    109101        .equal = 0,
    110102        .remove_callback = services_remove_callback
    … …  
    242234                /* Device node */
    243235               
    244                 unsigned long key[] = {
    245                         [SERVICES_KEY_HANDLE] = (unsigned long) node->service_id
    246                 };
    247                 link_t *lnk;
    248                
    249236                fibril_mutex_lock(&services_mutex);
     237                ht_link_t *lnk;
    250238restart:
    251                 lnk = hash_table_find(&services, key);
     239                lnk = hash_table_find(&services, &node->service_id);
    252240                if (lnk == NULL) {
    253241                        service_t *dev = (service_t *) malloc(sizeof(service_t));
    … …  
    292280                                 * entry and free the device structure.
    293281                                 */
    294                                 hash_table_remove(&services, key, SERVICES_KEYS);
     282                                hash_table_remove(&services, &node->service_id);
    295283                                fibril_mutex_unlock(&services_mutex);
    296284                               
    … …  
    301289                        dev->sess = sess;
    302290                } else {
    303                         service_t *dev = hash_table_get_instance(lnk, service_t, link);
     291                        service_t *dev = hash_table_get_inst(lnk, service_t, link);
    304292                       
    305293                        if (!dev->sess) {
    … …  
    463451bool locfs_init(void)
    464452{
    465         if (!hash_table_create(&services, 0,  SERVICES_KEYS, &services_ops))
     453        if (!hash_table_create(&services, 0,  0, &services_ops))
    466454                return false;
    467455       
    … …  
    567555                /* Device node */
    568556               
    569                 unsigned long key[] = {
    570                         [SERVICES_KEY_HANDLE] = (unsigned long) index
    571                 };
    572                
    573557                fibril_mutex_lock(&services_mutex);
    574                 link_t *lnk = hash_table_find(&services, key);
     558                ht_link_t *lnk = hash_table_find(&services, &index);
    575559                if (lnk == NULL) {
    576560                        fibril_mutex_unlock(&services_mutex);
    … …  
    578562                }
    579563               
    580                 service_t *dev = hash_table_get_instance(lnk, service_t, link);
     564                service_t *dev = hash_table_get_inst(lnk, service_t, link);
    581565                assert(dev->sess);
    582566               
    … …  
    633617        if (type == LOC_OBJECT_SERVICE) {
    634618                /* Device node */
    635                 unsigned long key[] = {
    636                         [SERVICES_KEY_HANDLE] = (unsigned long) index
    637                 };
    638619               
    639620                fibril_mutex_lock(&services_mutex);
    640                 link_t *lnk = hash_table_find(&services, key);
     621                ht_link_t *lnk = hash_table_find(&services, &index);
    641622                if (lnk == NULL) {
    642623                        fibril_mutex_unlock(&services_mutex);
    … …  
    644625                }
    645626               
    646                 service_t *dev = hash_table_get_instance(lnk, service_t, link);
     627                service_t *dev = hash_table_get_inst(lnk, service_t, link);
    647628                assert(dev->sess);
    648629               
    … …  
    703684       
    704685        if (type == LOC_OBJECT_SERVICE) {
    705                 unsigned long key[] = {
    706                         [SERVICES_KEY_HANDLE] = (unsigned long) index
    707                 };
    708686               
    709687                fibril_mutex_lock(&services_mutex);
    710                 link_t *lnk = hash_table_find(&services, key);
     688                ht_link_t *lnk = hash_table_find(&services, &index);
    711689                if (lnk == NULL) {
    712690                        fibril_mutex_unlock(&services_mutex);
    … …  
    714692                }
    715693               
    716                 service_t *dev = hash_table_get_instance(lnk, service_t, link);
     694                service_t *dev = hash_table_get_inst(lnk, service_t, link);
    717695                assert(dev->sess);
    718696                dev->refcount--;
    … …  
    720698                if (dev->refcount == 0) {
    721699                        async_hangup(dev->sess);
    722                         hash_table_remove(&services, key, SERVICES_KEYS);
     700                        hash_table_remove(&services, &index);
    723701                }
    724702               
    … …  
    744722       
    745723        if (type == LOC_OBJECT_SERVICE) {
    746                 unsigned long key[] = {
    747                         [SERVICES_KEY_HANDLE] = (unsigned long) index
    748                 };
    749                
     724
    750725                fibril_mutex_lock(&services_mutex);
    751                 link_t *lnk = hash_table_find(&services, key);
     726                ht_link_t *lnk = hash_table_find(&services, &index);
    752727                if (lnk == NULL) {
    753728                        fibril_mutex_unlock(&services_mutex);
    … …  
    755730                }
    756731               
    757                 service_t *dev = hash_table_get_instance(lnk, service_t, link);
     732                service_t *dev = hash_table_get_inst(lnk, service_t, link);
    758733                assert(dev->sess);
    759734               

  • uspace/srv/fs/mfs/mfs.h

    rb17518e rbc216a0  
    142142        unsigned refcnt;
    143143        fs_node_t *fsnode;
    144         link_t link;
     144        ht_link_t link;
    145145};
    146146

  • uspace/srv/fs/mfs/mfs_ops.c

    rb17518e rbc216a0  
    3535#include <align.h>
    3636#include <adt/hash_table.h>
     37#include <adt/hash.h>
    3738#include "mfs.h"
    3839
    39 #define OPEN_NODES_KEYS 2
    40 #define OPEN_NODES_SERVICE_KEY 0
    41 #define OPEN_NODES_INODE_KEY 1
    4240
    4341static bool check_magic_number(uint16_t magic, bool *native,
    … …  
    6058static int mfs_unlink(fs_node_t *, fs_node_t *, const char *name);
    6159static int mfs_destroy_node(fs_node_t *fn);
    62 static size_t open_nodes_hash(const link_t *item);
    63 static size_t open_nodes_key_hash(unsigned long key[]);
    64 static bool open_nodes_match(unsigned long key[], size_t keys,
    65     const link_t *item);
    6660static int mfs_node_get(fs_node_t **rfn, service_id_t service_id,
    6761    fs_index_t index);
    … …  
    9589/* Hash table interface for open nodes hash table */
    9690
     91typedef struct {
     92        service_id_t service_id;
     93        fs_index_t index;
     94} node_key_t;
     95
    9796static size_t
    98 open_nodes_key_hash(unsigned long key[])
    99 {
    100         /* As recommended by Effective Java, 2nd Edition. */
    101         size_t hash = 17;
    102         hash = 37 * hash + key[OPEN_NODES_SERVICE_KEY];
    103         hash = 37 * hash + key[OPEN_NODES_INODE_KEY];
    104         return hash;
     97open_nodes_key_hash(void *key)
     98{
     99        node_key_t *node_key = (node_key_t*)key;
     100        return hash_combine(node_key->service_id, node_key->index);
    105101}
    106102
    107103static size_t
    108 open_nodes_hash(const link_t *item)
    109 {
    110         struct mfs_node *m = hash_table_get_instance(item, struct mfs_node, link);
    111        
    112         unsigned long key[] = {
    113                 [OPEN_NODES_SERVICE_KEY] = m->instance->service_id,
    114                 [OPEN_NODES_INODE_KEY] = m->ino_i->index,
    115         };
    116        
    117         return open_nodes_key_hash(key);
     104open_nodes_hash(const ht_link_t *item)
     105{
     106        struct mfs_node *m = hash_table_get_inst(item, struct mfs_node, link);
     107        return hash_combine(m->instance->service_id, m->ino_i->index);
    118108}
    119109
    120110static bool
    121 open_nodes_match(unsigned long key[], size_t keys, const link_t *item)
    122 {
    123         assert(keys == 2);
    124         struct mfs_node *mnode = hash_table_get_instance(item, struct mfs_node, link);
    125        
    126         service_id_t service_id = ((service_id_t) key[OPEN_NODES_SERVICE_KEY]);
    127        
    128         return mnode->instance->service_id == service_id
    129                 && mnode->ino_i->index == key[OPEN_NODES_INODE_KEY];
    130 }
    131 
     111open_nodes_key_equal(void *key, const ht_link_t *item)
     112{
     113        node_key_t *node_key = (node_key_t*)key;
     114        struct mfs_node *mnode = hash_table_get_inst(item, struct mfs_node, link);
     115
     116        return node_key->service_id == mnode->instance->service_id
     117                && node_key->index == mnode->ino_i->index;
     118}
    132119
    133120static hash_table_ops_t open_nodes_ops = {
    134121        .hash = open_nodes_hash,
    135122        .key_hash = open_nodes_key_hash,
    136         .match = open_nodes_match,
     123        .key_equal = open_nodes_key_equal,
    137124        .equal = 0,
    138125        .remove_callback = 0,
    … …  
    142129mfs_global_init(void)
    143130{
    144         if (!hash_table_create(&open_nodes, 0, OPEN_NODES_KEYS, &open_nodes_ops)) {
     131        if (!hash_table_create(&open_nodes, 0, 0, &open_nodes_ops)) {
    145132                return ENOMEM;
    146133        }
    … …  
    413400        mnode->refcnt = 1;
    414401
    415         link_initialize(&mnode->link);
    416 
    417402        fibril_mutex_lock(&open_nodes_lock);
    418403        hash_table_insert(&open_nodes, &mnode->link);
    … …  
    515500        mnode->refcnt--;
    516501        if (mnode->refcnt == 0) {
    517                 unsigned long key[] = {
    518                         [OPEN_NODES_SERVICE_KEY] = mnode->instance->service_id,
    519                         [OPEN_NODES_INODE_KEY] = mnode->ino_i->index
    520                 };
    521                 hash_table_remove(&open_nodes, key, OPEN_NODES_KEYS);
     502                hash_table_remove_item(&open_nodes, &mnode->link);
    522503                assert(mnode->instance->open_nodes_cnt > 0);
    523504                mnode->instance->open_nodes_cnt--;
    … …  
    578559
    579560        /* Check if the node is not already open */
    580         unsigned long key[] = {
    581                 [OPEN_NODES_SERVICE_KEY] = inst->service_id,
    582                 [OPEN_NODES_INODE_KEY] = index,
     561        node_key_t key = {
     562                .service_id = inst->service_id,
     563                .index = index
    583564        };
    584         link_t *already_open = hash_table_find(&open_nodes, key);
     565       
     566        ht_link_t *already_open = hash_table_find(&open_nodes, &key);
    585567
    586568        if (already_open) {
    587                 mnode = hash_table_get_instance(already_open, struct mfs_node, link);
     569                mnode = hash_table_get_inst(already_open, struct mfs_node, link);
    588570                *rfn = mnode->fsnode;
    589571                mnode->refcnt++;
    … …  
    616598        mnode->ino_i = ino_i;
    617599        mnode->refcnt = 1;
    618         link_initialize(&mnode->link);
    619600
    620601        mnode->instance = inst;

  • uspace/srv/fs/tmpfs/tmpfs.h

    rb17518e rbc216a0  
    6262        fs_index_t index;       /**< TMPFS node index. */
    6363        service_id_t service_id;/**< Service ID of block device. */
    64         link_t nh_link;         /**< Nodes hash table link. */
     64        ht_link_t nh_link;              /**< Nodes hash table link. */
    6565        tmpfs_dentry_type_t type;
    6666        unsigned lnkcnt;        /**< Link count. */

  • uspace/srv/fs/tmpfs/tmpfs_ops.c

    rb17518e rbc216a0  
    5050#include <sys/types.h>
    5151#include <adt/hash_table.h>
     52#include <adt/hash.h>
    5253#include <as.h>
    5354#include <libfs.h>
    … …  
    140141hash_table_t nodes;
    141142
    142 #define NODES_KEY_DEV   0       
    143 #define NODES_KEY_INDEX 1
    144 
    145 /* Implementation of hash table interface for the nodes hash table. */
    146 static size_t nodes_key_hash(unsigned long key[])
    147 {
    148         /* Based on Effective Java, 2nd Edition. */
    149         size_t hash = 17;
    150         hash = 37 * hash + key[NODES_KEY_DEV];
    151         hash = 37 * hash + key[NODES_KEY_INDEX];
    152         return hash;
    153 }
    154 
    155 static size_t nodes_hash(const link_t *item)
    156 {
    157         tmpfs_node_t *nodep = hash_table_get_instance(item, tmpfs_node_t, nh_link);
    158        
    159         unsigned long key[] = {
    160                 [NODES_KEY_DEV] = nodep->service_id,
    161                 [NODES_KEY_INDEX] = nodep->index
    162         };
    163        
    164         return nodes_key_hash(key);
    165 }
    166 
    167 static bool nodes_match(unsigned long key[], size_t keys, const link_t *item)
    168 {
    169         tmpfs_node_t *nodep = hash_table_get_instance(item, tmpfs_node_t,
    170             nh_link);
    171        
    172         switch (keys) {
    173         case 1:
    174                 return (nodep->service_id == key[NODES_KEY_DEV]);
    175         case 2:
    176                 return ((nodep->service_id == key[NODES_KEY_DEV]) &&
    177                     (nodep->index == key[NODES_KEY_INDEX]));
    178         default:
    179                 assert((keys == 1) || (keys == 2));
    180         }
    181 
    182         return 0;
    183 }
    184 
    185 static void nodes_remove_callback(link_t *item)
    186 {
    187         tmpfs_node_t *nodep = hash_table_get_instance(item, tmpfs_node_t,
    188             nh_link);
     143/*
     144 * Implementation of hash table interface for the nodes hash table.
     145 */
     146
     147typedef struct {
     148        service_id_t service_id;
     149        fs_index_t index;
     150} node_key_t;
     151
     152static size_t nodes_key_hash(void *k)
     153{
     154        node_key_t *key = (node_key_t *)k;
     155        return hash_combine(key->service_id, key->index);
     156}
     157
     158static size_t nodes_hash(const ht_link_t *item)
     159{
     160        tmpfs_node_t *nodep = hash_table_get_inst(item, tmpfs_node_t, nh_link);
     161        return hash_combine(nodep->service_id, nodep->index);
     162}
     163
     164static bool nodes_key_equal(void *key_arg, const ht_link_t *item)
     165{
     166        tmpfs_node_t *node = hash_table_get_inst(item, tmpfs_node_t, nh_link);
     167        node_key_t *key = (node_key_t *)key_arg;
     168       
     169        return key->service_id == node->service_id && key->index == node->index;
     170}
     171
     172static void nodes_remove_callback(ht_link_t *item)
     173{
     174        tmpfs_node_t *nodep = hash_table_get_inst(item, tmpfs_node_t, nh_link);
    189175
    190176        while (!list_empty(&nodep->cs_list)) {
    … …  
    209195        .hash = nodes_hash,
    210196        .key_hash = nodes_key_hash,
    211         .match = nodes_match,
     197        .key_equal = nodes_key_equal,
    212198        .equal = 0,
    213199        .remove_callback = nodes_remove_callback
    … …  
    223209        nodep->size = 0;
    224210        nodep->data = NULL;
    225         link_initialize(&nodep->nh_link);
    226211        list_initialize(&nodep->cs_list);
    227212}
    … …  
    236221bool tmpfs_init(void)
    237222{
    238         if (!hash_table_create(&nodes, 0, 2, &nodes_ops))
     223        if (!hash_table_create(&nodes, 0, 0, &nodes_ops))
    239224                return false;
    240225       
    … …  
    254239}
    255240
     241static bool rm_service_id_nodes(ht_link_t *item, void *arg)
     242{
     243        service_id_t sid = *(service_id_t*)arg;
     244        tmpfs_node_t *node = hash_table_get_inst(item, tmpfs_node_t, nh_link);
     245       
     246        if (node->service_id == sid) {
     247                hash_table_remove_item(&nodes, &node->nh_link);
     248        }
     249        return true;
     250}
     251
    256252static void tmpfs_instance_done(service_id_t service_id)
    257 {
    258         unsigned long key[] = {
    259                 [NODES_KEY_DEV] = service_id
    260         };
    261         /*
    262          * Here we are making use of one special feature of our hash table
    263          * implementation, which allows to remove more items based on a partial
    264          * key match. In the following, we are going to remove all nodes
    265          * matching our device handle. The nodes_remove_callback() function will
    266          * take care of resource deallocation.
    267          */
    268         hash_table_remove(&nodes, key, 1);
     253{       
     254        hash_table_apply(&nodes, rm_service_id_nodes, &service_id);
    269255}
    270256
    … …  
    288274int tmpfs_node_get(fs_node_t **rfn, service_id_t service_id, fs_index_t index)
    289275{
    290         unsigned long key[] = {
    291                 [NODES_KEY_DEV] = service_id,
    292                 [NODES_KEY_INDEX] = index
     276        node_key_t key = {
     277                .service_id = service_id,
     278                .index = index
    293279        };
    294         link_t *lnk = hash_table_find(&nodes, key);
     280       
     281        ht_link_t *lnk = hash_table_find(&nodes, &key);
     282       
    295283        if (lnk) {
    296284                tmpfs_node_t *nodep;
    297                 nodep = hash_table_get_instance(lnk, tmpfs_node_t, nh_link);
     285                nodep = hash_table_get_inst(lnk, tmpfs_node_t, nh_link);
    298286                *rfn = FS_NODE(nodep);
    299287        } else {
    … …  
    358346        assert(!nodep->lnkcnt);
    359347        assert(list_empty(&nodep->cs_list));
    360 
    361         unsigned long key[] = {
    362                 [NODES_KEY_DEV] = nodep->service_id,
    363                 [NODES_KEY_INDEX] = nodep->index
    364         };
    365         hash_table_remove(&nodes, key, 2);
     348       
     349        hash_table_remove_item(&nodes, &nodep->nh_link);
    366350
    367351        /*
    … …  
    488472         * Lookup the respective TMPFS node.
    489473         */
    490         link_t *hlp;
    491         unsigned long key[] = {
    492                 [NODES_KEY_DEV] = service_id,
    493                 [NODES_KEY_INDEX] = index
     474        node_key_t key = {
     475                .service_id = service_id,
     476                .index = index
    494477        };
    495         hlp = hash_table_find(&nodes, key);
     478       
     479        ht_link_t *hlp = hash_table_find(&nodes, &key);
    496480        if (!hlp)
    497481                return ENOENT;
    498         tmpfs_node_t *nodep = hash_table_get_instance(hlp, tmpfs_node_t,
    499             nh_link);
     482       
     483        tmpfs_node_t *nodep = hash_table_get_inst(hlp, tmpfs_node_t, nh_link);
    500484       
    501485        /*
    … …  
    550534         * Lookup the respective TMPFS node.
    551535         */
    552         link_t *hlp;
    553         unsigned long key[] = {
    554                 [NODES_KEY_DEV] = service_id,
    555                 [NODES_KEY_INDEX] = index
     536        node_key_t key = {
     537                .service_id = service_id,
     538                .index = index
    556539        };
    557         hlp = hash_table_find(&nodes, key);
     540       
     541        ht_link_t *hlp = hash_table_find(&nodes, &key);
     542       
    558543        if (!hlp)
    559544                return ENOENT;
    560         tmpfs_node_t *nodep = hash_table_get_instance(hlp, tmpfs_node_t,
    561             nh_link);
     545       
     546        tmpfs_node_t *nodep = hash_table_get_inst(hlp, tmpfs_node_t, nh_link);
    562547
    563548        /*
    … …  
    612597         * Lookup the respective TMPFS node.
    613598         */
    614         unsigned long key[] = {
    615                 [NODES_KEY_DEV] = service_id,
    616                 [NODES_KEY_INDEX] = index
     599        node_key_t key = {
     600                .service_id = service_id,
     601                .index = index
    617602        };
    618         link_t *hlp = hash_table_find(&nodes, key);
     603       
     604        ht_link_t *hlp = hash_table_find(&nodes, &key);
     605       
    619606        if (!hlp)
    620607                return ENOENT;
    621         tmpfs_node_t *nodep = hash_table_get_instance(hlp, tmpfs_node_t, nh_link);
     608        tmpfs_node_t *nodep = hash_table_get_inst(hlp, tmpfs_node_t, nh_link);
    622609       
    623610        if (size == nodep->size)
    … …  
    648635static int tmpfs_destroy(service_id_t service_id, fs_index_t index)
    649636{
    650         link_t *hlp;
    651         unsigned long key[] = {
    652                 [NODES_KEY_DEV] = service_id,
    653                 [NODES_KEY_INDEX] = index
     637        node_key_t key = {
     638                .service_id = service_id,
     639                .index = index
    654640        };
    655         hlp = hash_table_find(&nodes, key);
     641       
     642        ht_link_t *hlp = hash_table_find(&nodes, &key);
    656643        if (!hlp)
    657644                return ENOENT;
    658         tmpfs_node_t *nodep = hash_table_get_instance(hlp, tmpfs_node_t,
     645        tmpfs_node_t *nodep = hash_table_get_inst(hlp, tmpfs_node_t,
    659646            nh_link);
    660647        return tmpfs_destroy_node(FS_NODE(nodep));

  • uspace/srv/hid/input/generic/gsp.c

    rb17518e rbc216a0  
    5151#include <gsp.h>
    5252#include <adt/hash_table.h>
     53#include <adt/hash.h>
    5354#include <stdlib.h>
    5455#include <stdio.h>
    5556
    5657/*
    57  * Hash table operations for the transition function.
    58  */
    59 
    60 static size_t trans_op_hash(const link_t *item);
    61 static size_t trans_op_key_hash(unsigned long key[]);
    62 static bool trans_op_match(unsigned long key[], size_t keys, const link_t *item);
     58 * Transition function hash table operations.
     59 */
     60typedef struct {
     61        int old_state;
     62        int input;
     63} trans_key_t;
     64
     65static size_t trans_key_hash(void *key)
     66{
     67        trans_key_t *trans_key = (trans_key_t *)key;
     68        return hash_combine(trans_key->input, trans_key->old_state);
     69}
     70
     71static size_t trans_hash(const ht_link_t *item)
     72{
     73        gsp_trans_t *t = hash_table_get_inst(item, gsp_trans_t, link);
     74        return hash_combine(t->input, t->old_state);
     75}
     76
     77static bool trans_key_equal(void *key, const ht_link_t *item)
     78{
     79        trans_key_t *trans_key = (trans_key_t *)key;
     80        gsp_trans_t *t = hash_table_get_inst(item, gsp_trans_t, link);
     81       
     82        return trans_key->input == t->input && trans_key->old_state == t->old_state;
     83}
    6384
    6485static hash_table_ops_t trans_ops = {
    65         .hash = trans_op_hash,
    66         .key_hash = trans_op_key_hash,
    67         .match = trans_op_match,
     86        .hash = trans_hash,
     87        .key_hash = trans_key_hash,
     88        .key_equal = trans_key_equal,
    6889        .equal = 0,
    6990        .remove_callback = 0
    7091};
    7192
     93
    7294static gsp_trans_t *trans_lookup(gsp_t *p, int state, int input);
    7395static void trans_insert(gsp_t *p, gsp_trans_t *t);
    … …  
    78100{
    79101        p->states = 1;
    80         hash_table_create(&p->trans, 0, 2, &trans_ops);
     102        hash_table_create(&p->trans, 0, 0, &trans_ops);
    81103}
    82104
    … …  
    222244static gsp_trans_t *trans_lookup(gsp_t *p, int state, int input)
    223245{
    224         link_t *item;
    225         unsigned long key[2];
    226 
    227         key[0] = state;
    228         key[1] = input;
    229 
    230         item = hash_table_find(&p->trans, key);
     246        ht_link_t *item;
     247       
     248        trans_key_t key = {
     249                .input = input,
     250                .old_state = state
     251        };
     252
     253        item = hash_table_find(&p->trans, &key);
    231254        if (item == NULL) return NULL;
    232255
    233         return hash_table_get_instance(item, gsp_trans_t, link);
     256        return hash_table_get_inst(item, gsp_trans_t, link);
    234257}
    235258
    … …  
    258281}
    259282
    260 /*
    261  * Transition function hash table operations.
    262  */
    263 
    264 static size_t trans_op_key_hash(unsigned long key[])
    265 {
    266         return (key[0] * 17 + key[1]);
    267 }
    268 
    269 static size_t trans_op_hash(const link_t *item)
    270 {
    271         gsp_trans_t *t = hash_table_get_instance(item, gsp_trans_t, link);
    272         unsigned long key[] = {
    273                 t->old_state,
    274                 t->input
    275         };
    276        
    277         return trans_op_key_hash(key);
    278 }
    279 
    280 static bool trans_op_match(unsigned long key[], size_t keys, const link_t *item)
    281 {
    282         gsp_trans_t *t = hash_table_get_instance(item, gsp_trans_t, link);
    283         return ((key[0] == (unsigned long) t->old_state)
    284             && (key[1] == (unsigned long) t->input));
    285 }
    286283
    287284/**

  • uspace/srv/hid/input/include/gsp.h

    rb17518e rbc216a0  
    5656/** Scancode parser transition. */
    5757typedef struct {
    58         link_t link;            /**< Link to hash table in @c gsp_t */
     58        ht_link_t link;         /**< Link to hash table in @c gsp_t */
    5959
    6060        /* Preconditions */

  • uspace/srv/ns/service.c

    rb17518e rbc216a0  
    4343/** Service hash table item. */
    4444typedef struct {
    45         link_t link;
     45        ht_link_t link;
    4646        sysarg_t service;        /**< Service ID. */
    4747        sysarg_t phone;          /**< Phone registered with the service. */
    … …  
    4949} hashed_service_t;
    5050
    51 /** Compute hash index into service hash table.
    52  *
    53  * @param key Pointer keys. However, only the first key (i.e. service number)
    54  *            is used to compute the hash index.
    55  *
    56  * @return Hash index corresponding to key[0].
    57  *
    58  */
    59 static size_t service_key_hash(unsigned long key[])
     51
     52static size_t service_key_hash(void *key)
    6053{
    61         assert(key);
    62         return key[0];
     54        return *(sysarg_t*)key;
    6355}
    6456
    65 static size_t service_hash(const link_t *item)
     57static size_t service_hash(const ht_link_t *item)
    6658{
    67         hashed_service_t *hs = hash_table_get_instance(item, hashed_service_t, link);
    68         unsigned long key = hs->service;
    69         return service_key_hash(&key);
     59        hashed_service_t *hs = hash_table_get_inst(item, hashed_service_t, link);
     60        return hs->service;
    7061}
    7162
    72 /** Compare a key with hashed item.
    73  *
    74  * This compare function always ignores the third key.
    75  * It exists only to make it possible to remove records
    76  * originating from connection with key[1] in_phone_hash
    77  * value. Note that this is close to being classified
    78  * as a nasty hack.
    79  *
    80  * @param key  Array of keys.
    81  * @param keys Must be lesser or equal to 3.
    82  * @param item Pointer to a hash table item.
    83  *
    84  * @return Non-zero if the key matches the item, zero otherwise.
    85  *
    86  */
    87 static bool service_match(unsigned long key[], size_t keys, const link_t *item)
     63static bool service_key_equal(void *key, const ht_link_t *item)
    8864{
    89         assert(key);
    90         assert(keys <= 3);
    91         assert(item);
    92        
    93         hashed_service_t *hs = hash_table_get_instance(item, hashed_service_t, link);
    94        
    95         if (keys == 2)
    96                 return ((key[0] == hs->service) && (key[1] == hs->in_phone_hash));
    97         else
    98                 return (key[0] == hs->service);
    99 }
    100 
    101 /** Perform actions after removal of item from the hash table.
    102  *
    103  * @param item Item that was removed from the hash table.
    104  *
    105  */
    106 static void service_remove(link_t *item)
    107 {
    108         assert(item);
    109         free(hash_table_get_instance(item, hashed_service_t, link));
     65        hashed_service_t *hs = hash_table_get_inst(item, hashed_service_t, link);
     66        return hs->service == *(sysarg_t*)key;
    11067}
    11168
    … …  
    11471        .hash = service_hash,
    11572        .key_hash = service_key_hash,
    116         .match = service_match,
     73        .key_equal = service_key_equal,
    11774        .equal = 0,
    118         .remove_callback = service_remove
     75        .remove_callback = 0
    11976};
    12077
    … …  
    13592int service_init(void)
    13693{
    137         if (!hash_table_create(&service_hash_table, 0, 3, &service_hash_table_ops)) {
     94        if (!hash_table_create(&service_hash_table, 0, 0, &service_hash_table_ops)) {
    13895                printf(NAME ": No memory available for services\n");
    13996                return ENOMEM;
    … …  
    152109                pending_conn_t *pr = list_get_instance(cur, pending_conn_t, link);
    153110               
    154                 unsigned long keys[3] = {
    155                         pr->service,
    156                         0,
    157                         0
    158                 };
    159                
    160                 link_t *link = hash_table_find(&service_hash_table, keys);
     111                ht_link_t *link = hash_table_find(&service_hash_table, &pr->service);
    161112                if (!link)
    162113                        continue;
    163114               
    164                 hashed_service_t *hs = hash_table_get_instance(link, hashed_service_t, link);
     115                hashed_service_t *hs = hash_table_get_inst(link, hashed_service_t, link);
    165116                (void) ipc_forward_fast(pr->callid, hs->phone, pr->arg2,
    166117                    pr->arg3, 0, IPC_FF_NONE);
    … …  
    183134int register_service(sysarg_t service, sysarg_t phone, ipc_call_t *call)
    184135{
    185         unsigned long keys[3] = {
    186                 service,
    187                 call->in_phone_hash,
    188                 0
    189         };
    190        
    191         if (hash_table_find(&service_hash_table, keys))
     136        if (hash_table_find(&service_hash_table, &service))
    192137                return EEXISTS;
    193138       
    … …  
    196141                return ENOMEM;
    197142       
    198         link_initialize(&hs->link);
    199143        hs->service = service;
    200144        hs->phone = phone;
    … …  
    217161{
    218162        sysarg_t retval;
    219         unsigned long keys[3] = {
    220                 service,
    221                 0,
    222                 0
    223         };
    224163       
    225         link_t *link = hash_table_find(&service_hash_table, keys);
     164        ht_link_t *link = hash_table_find(&service_hash_table, &service);
    226165        if (!link) {
    227166                if (IPC_GET_ARG4(*call) & IPC_FLAG_BLOCKING) {
    … …  
    246185        }
    247186       
    248         hashed_service_t *hs = hash_table_get_instance(link, hashed_service_t, link);
     187        hashed_service_t *hs = hash_table_get_inst(link, hashed_service_t, link);
    249188        (void) ipc_forward_fast(callid, hs->phone, IPC_GET_ARG2(*call),
    250189            IPC_GET_ARG3(*call), 0, IPC_FF_NONE);

  • uspace/srv/ns/task.c

    rb17518e rbc216a0  
    5353/** Task hash table item. */
    5454typedef struct {
    55         link_t link;
     55        ht_link_t link;
    5656       
    5757        task_id_t id;    /**< Task ID. */
    … …  
    6161} hashed_task_t;
    6262
    63 /** Compute hash index into task hash table.
    64  *
    65  * @param key Pointer keys. However, only the first key (i.e. truncated task
    66  *            number) is used to compute the hash index.
    67  *
    68  * @return Hash index corresponding to key[0].
    69  *
    70  */
    71 static size_t task_key_hash(unsigned long key[])
    72 {
    73         size_t hash = 17;
    74         hash = 37 * hash + key[1];
    75         hash = 37 * hash + key[0];
    76         return hash;
    77 }
    78 
    79 static size_t task_hash(const link_t *item)
    80 {
    81         hashed_task_t *ht = hash_table_get_instance(item, hashed_task_t, link);
    82 
    83         unsigned long key[] = {
    84                 LOWER32(ht->id),
    85                 UPPER32(ht->id)
    86         };
    87        
    88         return task_key_hash(key);
    89 }
    90 
    91 /** Compare a key with hashed item.
    92  *
    93  * @param key  Array of keys.
    94  * @param keys Must be less than or equal to 2.
    95  * @param item Pointer to a hash table item.
    96  *
    97  * @return Non-zero if the key matches the item, zero otherwise.
    98  *
    99  */
    100 static bool task_match(unsigned long key[], size_t keys, const link_t *item)
    101 {
    102         assert(key);
    103         assert(keys == 2);
    104         assert(item);
    105        
    106         hashed_task_t *ht = hash_table_get_instance(item, hashed_task_t, link);
    107        
    108         return (key[0] == LOWER32(ht->id))
    109                 && (key[1] == UPPER32(ht->id));
    110 }
    111 
    112 /** Perform actions after removal of item from the hash table.
    113  *
    114  * @param item Item that was removed from the hash table.
    115  *
    116  */
    117 static void task_remove(link_t *item)
    118 {
    119         assert(item);
    120         free(hash_table_get_instance(item, hashed_task_t, link));
     63
     64static size_t task_key_hash(void *key)
     65{
     66        return *(task_id_t*)key;
     67}
     68
     69static size_t task_hash(const ht_link_t  *item)
     70{
     71        hashed_task_t *ht = hash_table_get_inst(item, hashed_task_t, link);
     72        return ht->id;
     73}
     74
     75static bool task_key_equal(void *key, const ht_link_t *item)
     76{
     77        hashed_task_t *ht = hash_table_get_inst(item, hashed_task_t, link);
     78        return ht->id == *(task_id_t*)key;
     79}
     80
     81/** Perform actions after removal of item from the hash table. */
     82static void task_remove(ht_link_t *item)
     83{
     84        free(hash_table_get_inst(item, hashed_task_t, link));
    12185}
    12286
    … …  
    12589        .hash = task_hash,
    12690        .key_hash = task_key_hash,
    127         .match = task_match,
     91        .key_equal = task_key_equal,
    12892        .equal = 0,
    12993        .remove_callback = task_remove
    … …  
    13498
    13599typedef struct {
    136         link_t link;
     100        ht_link_t link;
    137101        sysarg_t in_phone_hash;  /**< Incoming phone hash. */
    138102        task_id_t id;            /**< Task ID. */
    139103} p2i_entry_t;
    140104
    141 /** Compute hash index into task hash table.
    142  *
    143  * @param key Array of keys.
    144  *
    145  * @return Hash index corresponding to key[0].
    146  *
    147  */
    148 static size_t p2i_key_hash(unsigned long key[])
    149 {
    150         assert(key);
    151         return key[0];
    152 }
    153 
    154 static size_t p2i_hash(const link_t *item)
    155 {
    156         p2i_entry_t *entry = hash_table_get_instance(item, p2i_entry_t, link);
    157         unsigned long key = entry->in_phone_hash;
    158         return p2i_key_hash(&key);
    159 }
    160 
    161 /** Compare a key with hashed item.
    162  *
    163  * @param key  Array of keys.
    164  * @param keys Must be less than or equal to 1.
    165  * @param item Pointer to a hash table item.
    166  *
    167  * @return Non-zero if the key matches the item, zero otherwise.
    168  *
    169  */
    170 static bool p2i_match(unsigned long key[], size_t keys, const link_t *item)
    171 {
    172         assert(key);
    173         assert(keys == 1);
     105/* phone-to-id hash table operations */
     106
     107static size_t p2i_key_hash(void *key)
     108{
     109        sysarg_t in_phone_hash = *(sysarg_t*)key;
     110        return in_phone_hash;
     111}
     112
     113static size_t p2i_hash(const ht_link_t *item)
     114{
     115        p2i_entry_t *entry = hash_table_get_inst(item, p2i_entry_t, link);
     116        return entry->in_phone_hash;
     117}
     118
     119static bool p2i_key_equal(void *key, const ht_link_t *item)
     120{
     121        sysarg_t in_phone_hash = *(sysarg_t*)key;
     122        p2i_entry_t *entry = hash_table_get_inst(item, p2i_entry_t, link);
     123       
     124        return (in_phone_hash == entry->in_phone_hash);
     125}
     126
     127/** Perform actions after removal of item from the hash table.
     128 *
     129 * @param item Item that was removed from the hash table.
     130 *
     131 */
     132static void p2i_remove(ht_link_t *item)
     133{
    174134        assert(item);
    175        
    176         p2i_entry_t *entry = hash_table_get_instance(item, p2i_entry_t, link);
    177        
    178         return (key[0] == entry->in_phone_hash);
    179 }
    180 
    181 /** Perform actions after removal of item from the hash table.
    182  *
    183  * @param item Item that was removed from the hash table.
    184  *
    185  */
    186 static void p2i_remove(link_t *item)
    187 {
    188         assert(item);
    189         free(hash_table_get_instance(item, p2i_entry_t, link));
     135        free(hash_table_get_inst(item, p2i_entry_t, link));
    190136}
    191137
    … …  
    194140        .hash = p2i_hash,
    195141        .key_hash = p2i_key_hash,
    196         .match = p2i_match,
     142        .key_equal = p2i_key_equal,
    197143        .equal = 0,
    198144        .remove_callback = p2i_remove
    … …  
    213159int task_init(void)
    214160{
    215         if (!hash_table_create(&task_hash_table, 0, 2, &task_hash_table_ops)) {
     161        if (!hash_table_create(&task_hash_table, 0, 0, &task_hash_table_ops)) {
    216162                printf(NAME ": No memory available for tasks\n");
    217163                return ENOMEM;
    218164        }
    219165       
    220         if (!hash_table_create(&phone_to_id, 0, 1, &p2i_ops)) {
     166        if (!hash_table_create(&phone_to_id, 0, 0, &p2i_ops)) {
    221167                printf(NAME ": No memory available for tasks\n");
    222168                return ENOMEM;
    … …  
    236182                pending_wait_t *pr = list_get_instance(cur, pending_wait_t, link);
    237183               
    238                 unsigned long keys[2] = {
    239                         LOWER32(pr->id),
    240                         UPPER32(pr->id)
    241                 };
    242                
    243                 link_t *link = hash_table_find(&task_hash_table, keys);
     184                ht_link_t *link = hash_table_find(&task_hash_table, &pr->id);
    244185                if (!link)
    245186                        continue;
    246187               
    247                 hashed_task_t *ht = hash_table_get_instance(link, hashed_task_t, link);
     188                hashed_task_t *ht = hash_table_get_inst(link, hashed_task_t, link);
    248189                if (!ht->finished)
    249190                        continue;
    … …  
    256197                }
    257198               
    258                 hash_table_remove(&task_hash_table, keys, 2);
     199                hash_table_remove(&task_hash_table, &pr->id);
    259200                list_remove(cur);
    260201                free(pr);
    … …  
    268209        task_exit_t texit;
    269210       
    270         unsigned long keys[2] = {
    271                 LOWER32(id),
    272                 UPPER32(id)
    273         };
    274        
    275         link_t *link = hash_table_find(&task_hash_table, keys);
     211        ht_link_t *link = hash_table_find(&task_hash_table, &id);
    276212        hashed_task_t *ht = (link != NULL) ?
    277             hash_table_get_instance(link, hashed_task_t, link) : NULL;
     213            hash_table_get_inst(link, hashed_task_t, link) : NULL;
    278214       
    279215        if (ht == NULL) {
    … …  
    299235        }
    300236       
    301         hash_table_remove(&task_hash_table, keys, 2);
     237        hash_table_remove_item(&task_hash_table, link);
    302238        retval = EOK;
    303239       
    … …  
    314250        task_id_t id = MERGE_LOUP32(IPC_GET_ARG1(*call), IPC_GET_ARG2(*call));
    315251
    316         unsigned long keys[] = { call->in_phone_hash };
    317        
    318         link_t *link = hash_table_find(&phone_to_id, keys);
     252        ht_link_t *link = hash_table_find(&phone_to_id, &call->in_phone_hash);
    319253        if (link != NULL)
    320254                return EEXISTS;
    … …  
    332266         */
    333267       
    334         link_initialize(&entry->link);
    335268        entry->in_phone_hash = call->in_phone_hash;
    336269        entry->id = id;
    … …  
    341274         */
    342275       
    343         link_initialize(&ht->link);
    344276        ht->id = id;
    345277        ht->finished = false;
    … …  
    353285static int get_id_by_phone(sysarg_t phone_hash, task_id_t *id)
    354286{
    355         unsigned long keys[1] = {phone_hash};
    356        
    357         link_t *link = hash_table_find(&phone_to_id, keys);
     287        ht_link_t *link = hash_table_find(&phone_to_id, &phone_hash);
    358288        if (link == NULL)
    359289                return ENOENT;
    360290       
    361         p2i_entry_t *entry = hash_table_get_instance(link, p2i_entry_t, link);
     291        p2i_entry_t *entry = hash_table_get_inst(link, p2i_entry_t, link);
    362292        *id = entry->id;
    363293       
    … …  
    372302                return rc;
    373303       
    374         unsigned long keys[2] = {
    375                 LOWER32(id),
    376                 UPPER32(id)
    377         };
    378        
    379         link_t *link = hash_table_find(&task_hash_table, keys);
     304        ht_link_t *link = hash_table_find(&task_hash_table, &id);
    380305        hashed_task_t *ht = (link != NULL) ?
    381             hash_table_get_instance(link, hashed_task_t, link) : NULL;
     306            hash_table_get_inst(link, hashed_task_t, link) : NULL;
    382307       
    383308        if ((ht == NULL) || (ht->finished))
    … …  
    393318int ns_task_disconnect(ipc_call_t *call)
    394319{
    395         unsigned long keys[2];
    396        
    397320        task_id_t id;
    398321        int rc = get_id_by_phone(call->in_phone_hash, &id);
    … …  
    401324       
    402325        /* Delete from phone-to-id map. */
    403         keys[0] = call->in_phone_hash;
    404         hash_table_remove(&phone_to_id, keys, 1);
     326        hash_table_remove(&phone_to_id, &call->in_phone_hash);
    405327       
    406328        /* Mark task as finished. */
    407         keys[0] = LOWER32(id);
    408         keys[1] = UPPER32(id);
    409        
    410         link_t *link = hash_table_find(&task_hash_table, keys);
     329        ht_link_t *link = hash_table_find(&task_hash_table, &id);
    411330        if (link == NULL)
    412331                return EOK;
    413332
    414         hashed_task_t *ht =
    415             hash_table_get_instance(link, hashed_task_t, link);
     333        hashed_task_t *ht = hash_table_get_inst(link, hashed_task_t, link);
    416334       
    417335        ht->finished = true;

  • uspace/srv/vfs/vfs.h

    rb17518e rbc216a0  
    3636#include <async.h>
    3737#include <adt/list.h>
     38#include <adt/hash_table.h>
    3839#include <fibril_synch.h>
    3940#include <sys/types.h>
    … …  
    112113        unsigned lnkcnt;
    113114
    114         link_t nh_link;         /**< Node hash-table link. */
     115        ht_link_t nh_link;              /**< Node hash-table link. */
    115116
    116117        vfs_node_type_t type;   /**< Partial info about the node type. */

  • uspace/srv/vfs/vfs_node.c

    rb17518e rbc216a0  
    4141#include <fibril_synch.h>
    4242#include <adt/hash_table.h>
     43#include <adt/hash.h>
    4344#include <assert.h>
    4445#include <async.h>
    … …  
    5859#define KEY_INDEX       2
    5960
    60 static size_t nodes_key_hash(unsigned long []);
    61 static size_t nodes_hash(const link_t *);
    62 static bool nodes_match(unsigned long [], size_t, const link_t *);
     61static size_t nodes_key_hash(void *);
     62static size_t nodes_hash(const ht_link_t *);
     63static bool nodes_key_equal(void *, const ht_link_t *);
     64static vfs_triplet_t node_triplet(vfs_node_t *node);
    6365
    6466/** VFS node hash table operations. */
    … …  
    6668        .hash = nodes_hash,
    6769        .key_hash = nodes_key_hash,
    68         .match = nodes_match,
     70        .key_equal = nodes_key_equal,
    6971        .equal = 0,
    7072        .remove_callback = 0,
    … …  
    7779bool vfs_nodes_init(void)
    7880{
    79         return hash_table_create(&nodes, 0, 3, &nodes_ops);
     81        return hash_table_create(&nodes, 0, 0, &nodes_ops);
    8082}
    8183
    … …  
    116118                 */
    117119               
    118                 unsigned long key[] = {
    119                         [KEY_FS_HANDLE] = node->fs_handle,
    120                         [KEY_DEV_HANDLE] = node->service_id,
    121                         [KEY_INDEX] = node->index
    122                 };
    123                
    124                 hash_table_remove(&nodes, key, 3);
     120                hash_table_remove_item(&nodes, &node->nh_link);
    125121                free_vfs_node = true;
    126122               
    … …  
    160156{
    161157        fibril_mutex_lock(&nodes_mutex);
    162         unsigned long key[] = {
    163                 [KEY_FS_HANDLE] = node->fs_handle,
    164                 [KEY_DEV_HANDLE] = node->service_id,
    165                 [KEY_INDEX] = node->index
    166         };
    167         hash_table_remove(&nodes, key, 3);
     158        hash_table_remove_item(&nodes, &node->nh_link);
    168159        fibril_mutex_unlock(&nodes_mutex);
    169160        free(node);
    … …  
    184175vfs_node_t *vfs_node_get(vfs_lookup_res_t *result)
    185176{
    186         unsigned long key[] = {
    187                 [KEY_FS_HANDLE] = result->triplet.fs_handle,
    188                 [KEY_DEV_HANDLE] = result->triplet.service_id,
    189                 [KEY_INDEX] = result->triplet.index
    190         };
    191         link_t *tmp;
    192177        vfs_node_t *node;
    193178
    194179        fibril_mutex_lock(&nodes_mutex);
    195         tmp = hash_table_find(&nodes, key);
     180        ht_link_t *tmp = hash_table_find(&nodes, &result->triplet);
    196181        if (!tmp) {
    197182                node = (vfs_node_t *) malloc(sizeof(vfs_node_t));
    … …  
    207192                node->lnkcnt = result->lnkcnt;
    208193                node->type = result->type;
    209                 link_initialize(&node->nh_link);
    210194                fibril_rwlock_initialize(&node->contents_rwlock);
    211195                hash_table_insert(&nodes, &node->nh_link);
    212196        } else {
    213                 node = hash_table_get_instance(tmp, vfs_node_t, nh_link);
     197                node = hash_table_get_inst(tmp, vfs_node_t, nh_link);
    214198                if (node->type == VFS_NODE_UNKNOWN &&
    215199                    result->type != VFS_NODE_UNKNOWN) {
    … …  
    242226}
    243227
    244 size_t nodes_key_hash(unsigned long key[])
    245 {
    246         /* Combine into a hash like they do in Effective Java, 2nd edition. */
    247         size_t hash = 17;
    248         hash = 37 * hash + key[KEY_FS_HANDLE];
    249         hash = 37 * hash + key[KEY_DEV_HANDLE];
    250         hash = 37 * hash + key[KEY_INDEX];
    251         return hash;
    252 }
    253 
    254 size_t nodes_hash(const link_t *item)
    255 {
    256         vfs_node_t *node = hash_table_get_instance(item, vfs_node_t, nh_link);
    257        
    258         unsigned long key[] = {
    259                 [KEY_FS_HANDLE] = node->fs_handle,
    260                 [KEY_DEV_HANDLE] = node->service_id,
    261                 [KEY_INDEX] = node->index
    262         };
    263        
    264         return nodes_key_hash(key);
    265 }
    266 
    267 
    268 bool nodes_match(unsigned long key[], size_t keys, const link_t *item)
    269 {
    270         vfs_node_t *node = hash_table_get_instance(item, vfs_node_t, nh_link);
    271         return (node->fs_handle == (fs_handle_t) key[KEY_FS_HANDLE]) &&
    272             (node->service_id == key[KEY_DEV_HANDLE]) &&
    273             (node->index == key[KEY_INDEX]);
    274 }
    275 
    276 
    277228struct refcnt_data {
    278229        /** Sum of all reference counts for this file system instance. */
    … …  
    282233};
    283234
    284 static bool refcnt_visitor(link_t *item, void *arg)
    285 {
    286         vfs_node_t *node = hash_table_get_instance(item, vfs_node_t, nh_link);
     235static bool refcnt_visitor(ht_link_t *item, void *arg)
     236{
     237        vfs_node_t *node = hash_table_get_inst(item, vfs_node_t, nh_link);
    287238        struct refcnt_data *rd = (void *) arg;
    288239
    … …  
    332283}
    333284
     285
     286static size_t nodes_key_hash(void *key)
     287{
     288        vfs_triplet_t *tri = key;
     289        size_t hash = hash_combine(tri->fs_handle, tri->index);
     290        return hash_combine(hash, tri->service_id);
     291}
     292
     293static size_t nodes_hash(const ht_link_t *item)
     294{
     295        vfs_node_t *node = hash_table_get_inst(item, vfs_node_t, nh_link);
     296        vfs_triplet_t tri = node_triplet(node);
     297        return nodes_key_hash(&tri);
     298}
     299
     300static bool nodes_key_equal(void *key, const ht_link_t *item)
     301{
     302        vfs_triplet_t *tri = key;
     303        vfs_node_t *node = hash_table_get_inst(item, vfs_node_t, nh_link);
     304        return node->fs_handle == tri->fs_handle
     305                && node->service_id == tri->service_id
     306                && node->index == tri->index;
     307}
     308
     309static inline vfs_triplet_t node_triplet(vfs_node_t *node)
     310{
     311        vfs_triplet_t tri = {
     312                .fs_handle = node->fs_handle,
     313                .service_id = node->service_id,
     314                .index = node->index
     315        };
     316       
     317        return tri;
     318}
     319
    334320/**
    335321 * @}
Note: See TracChangeset for help on using the changeset viewer.