Changeset 0ca7286 in mainline


Ignore:
Timestamp:
2012-07-21T11:19:27Z (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:
2732c94
Parents:
1c1da4b
Message:

Added resizing to user space (single-threaded) hash_table. Resizes in a way to mitigate effects of bad hash functions. Change of interface affected many files.

Location:
uspace
Files:
23 edited

Legend:

Unmodified
Added
Removed

  • uspace/app/trace/ipcp.c

    r1c1da4b r0ca7286  
    3838#include <sys/typefmt.h>
    3939#include <abi/ipc/methods.h>
     40#include <macros.h>
    4041#include "ipc_desc.h"
    4142#include "proto.h"
    … …  
    6465int have_conn[MAX_PHONE];
    6566
    66 #define PCALL_TABLE_CHAINS 32
    67 hash_table_t pending_calls;
     67static hash_table_t pending_calls;
    6868
    6969/*
    … …  
    7373proto_t *proto_unknown;         /**< Protocol with no known methods. */
    7474
    75 static hash_index_t pending_call_hash(unsigned long key[]);
    76 static int pending_call_compare(unsigned long key[], hash_count_t keys,
    77     link_t *item);
    78 static void pending_call_remove_callback(link_t *item);
    79 
    80 hash_table_operations_t pending_call_ops = {
     75static size_t pending_call_key_hash(unsigned long key[]);
     76static size_t pending_call_hash(const link_t *item);
     77static bool pending_call_match(unsigned long key[], size_t keys,
     78    const link_t *item);
     79
     80static hash_table_ops_t pending_call_ops = {
    8181        .hash = pending_call_hash,
    82         .compare = pending_call_compare,
    83         .remove_callback = pending_call_remove_callback
     82        .key_hash = pending_call_key_hash,
     83        .match = pending_call_match,
     84        .equal = 0,
     85        .remove_callback = 0
    8486};
    8587
    8688
    87 static hash_index_t pending_call_hash(unsigned long key[])
    88 {
    89 //      printf("pending_call_hash\n");
    90         return key[0] % PCALL_TABLE_CHAINS;
    91 }
    92 
    93 static int pending_call_compare(unsigned long key[], hash_count_t keys,
    94     link_t *item)
    95 {
    96         pending_call_t *hs;
    97 
    98 //      printf("pending_call_compare\n");
    99         hs = hash_table_get_instance(item, pending_call_t, link);
    100 
    101         // FIXME: this will fail if sizeof(long) < sizeof(void *).
    102         return key[0] == hs->call_hash;
    103 }
    104 
    105 static void pending_call_remove_callback(link_t *item)
    106 {
    107 //      printf("pending_call_remove_callback\n");
    108 }
     89static 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
     97static 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
     107static 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
    109116
    110117
    … …  
    177184        }
    178185
    179         hash_table_create(&pending_calls, PCALL_TABLE_CHAINS, 1, &pending_call_ops);
     186        hash_table_create(&pending_calls, 0, 2, &pending_call_ops);
    180187}
    181188
    … …  
    190197        pending_call_t *pcall;
    191198        proto_t *proto;
    192         unsigned long key[1];
    193199        oper_t *oper;
    194200        sysarg_t *args;
    … …  
    254260        pcall->oper = oper;
    255261
    256         key[0] = hash;
    257 
    258         hash_table_insert(&pending_calls, key, &pcall->link);
     262        hash_table_insert(&pending_calls, &pcall->link);
    259263}
    260264
    … …  
    336340        link_t *item;
    337341        pending_call_t *pcall;
    338         unsigned long key[1];
    339342       
    340343        if ((hash & IPC_CALLID_ANSWERED) == 0 && hash != IPCP_CALLID_SYNC) {
    … …  
    347350       
    348351        hash = hash & ~IPC_CALLID_ANSWERED;
    349         key[0] = hash;
     352        unsigned long key[] = {
     353                LOWER32(hash),
     354                UPPER32(hash)
     355        };
    350356       
    351357        item = hash_table_find(&pending_calls, key);
    … …  
    358364       
    359365        pcall = hash_table_get_instance(item, pending_call_t, link);
    360         hash_table_remove(&pending_calls, key, 1);
     366        hash_table_remove(&pending_calls, key, 2);
    361367       
    362368        parse_answer(hash, pcall, call);

  • uspace/app/trace/proto.c

    r1c1da4b r0ca7286  
    4040#include "proto.h"
    4141
    42 #define SRV_PROTO_TABLE_CHAINS 32
    43 #define METHOD_OPER_TABLE_CHAINS 32
    44 
    45 hash_table_t srv_proto;
     42
     43/* Maps service number to protocol */
     44static hash_table_t srv_proto;
    4645
    4746typedef struct {
    … …  
    5756} method_oper_t;
    5857
    59 static hash_index_t srv_proto_hash(unsigned long key[]);
    60 static int srv_proto_compare(unsigned long key[], hash_count_t keys,
    61     link_t *item);
    62 static void srv_proto_remove_callback(link_t *item);
    63 
    64 hash_table_operations_t srv_proto_ops = {
     58
     59
     60
     61static size_t srv_proto_key_hash(unsigned long key[])
     62{
     63        return key[0];
     64}
     65
     66static 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
     73static 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;
     78}
     79
     80static hash_table_ops_t srv_proto_ops = {
    6581        .hash = srv_proto_hash,
    66         .compare = srv_proto_compare,
    67         .remove_callback = srv_proto_remove_callback
     82        .key_hash = srv_proto_key_hash,
     83        .match = srv_proto_match,
     84        .equal = 0,
     85        .remove_callback = 0
    6886};
    6987
    70 static hash_index_t method_oper_hash(unsigned long key[]);
    71 static int method_oper_compare(unsigned long key[], hash_count_t keys,
    72     link_t *item);
    73 static void method_oper_remove_callback(link_t *item);
    74 
    75 hash_table_operations_t method_oper_ops = {
     88
     89static size_t method_oper_key_hash(unsigned long key[])
     90{
     91        return key[0];
     92}
     93
     94static 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
     101static 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;
     107}
     108
     109static hash_table_ops_t method_oper_ops = {
    76110        .hash = method_oper_hash,
    77         .compare = method_oper_compare,
    78         .remove_callback = method_oper_remove_callback
     111        .key_hash = method_oper_key_hash,
     112        .match = method_oper_match,
     113        .equal = 0,
     114        .remove_callback = 0
    79115};
    80116
    81 static hash_index_t srv_proto_hash(unsigned long key[])
    82 {
    83         return key[0] % SRV_PROTO_TABLE_CHAINS;
    84 }
    85 
    86 static int srv_proto_compare(unsigned long key[], hash_count_t keys,
    87     link_t *item)
     117
     118void proto_init(void)
     119{
     120        hash_table_create(&srv_proto, 0, 1, &srv_proto_ops);
     121}
     122
     123void proto_cleanup(void)
     124{
     125        hash_table_destroy(&srv_proto);
     126}
     127
     128void proto_register(int srv, proto_t *proto)
    88129{
    89130        srv_proto_t *sp;
    90 
    91         sp = hash_table_get_instance(item, srv_proto_t, link);
    92 
    93         return key[0] == sp->srv;
    94 }
    95 
    96 static void srv_proto_remove_callback(link_t *item)
    97 {
    98 }
    99 
    100 static hash_index_t method_oper_hash(unsigned long key[])
    101 {
    102         return key[0] % METHOD_OPER_TABLE_CHAINS;
    103 }
    104 
    105 static int method_oper_compare(unsigned long key[], hash_count_t keys,
    106     link_t *item)
    107 {
    108         method_oper_t *mo;
    109 
    110         mo = hash_table_get_instance(item, method_oper_t, link);
    111 
    112         return key[0] == mo->method;
    113 }
    114 
    115 static void method_oper_remove_callback(link_t *item)
    116 {
    117 }
    118 
    119 
    120 void proto_init(void)
    121 {
    122         hash_table_create(&srv_proto, SRV_PROTO_TABLE_CHAINS, 1,
    123             &srv_proto_ops);
    124 }
    125 
    126 void proto_cleanup(void)
    127 {
    128         hash_table_destroy(&srv_proto);
    129 }
    130 
    131 void proto_register(int srv, proto_t *proto)
    132 {
    133         srv_proto_t *sp;
    134         unsigned long key;
    135131
    136132        sp = malloc(sizeof(srv_proto_t));
    137133        sp->srv = srv;
    138134        sp->proto = proto;
    139         key = srv;
    140 
    141         hash_table_insert(&srv_proto, &key, &sp->link);
     135
     136        hash_table_insert(&srv_proto, &sp->link);
    142137}
    143138
    144139proto_t *proto_get_by_srv(int srv)
    145140{
    146         unsigned long key;
    147141        link_t *item;
    148142        srv_proto_t *sp;
    149143
    150         key = srv;
     144        unsigned long key = srv;
    151145        item = hash_table_find(&srv_proto, &key);
    152146        if (item == NULL) return NULL;
    … …  
    159153{
    160154        proto->name = name;
    161         hash_table_create(&proto->method_oper, SRV_PROTO_TABLE_CHAINS, 1,
    162             &method_oper_ops);
     155        hash_table_create(&proto->method_oper, 0, 1, &method_oper_ops);
    163156}
    164157
    … …  
    181174{
    182175        method_oper_t *mo;
    183         unsigned long key;
    184176
    185177        mo = malloc(sizeof(method_oper_t));
    186178        mo->method = method;
    187179        mo->oper = oper;
    188         key = method;
    189 
    190         hash_table_insert(&proto->method_oper, &key, &mo->link);       
     180
     181        hash_table_insert(&proto->method_oper, &mo->link);     
    191182}
    192183

  • uspace/app/trace/proto.h

    r1c1da4b r0ca7286  
    6262} proto_t;
    6363
    64 /* Maps service number to protocol */
    65 extern hash_table_t srv_proto;
    6664
    6765extern void proto_init(void);

  • uspace/lib/block/libblock.c

    r1c1da4b r0ca7286  
    6262static LIST_INITIALIZE(dcl);
    6363
    64 #define CACHE_BUCKETS_LOG2  10
    65 #define CACHE_BUCKETS       (1 << CACHE_BUCKETS_LOG2)
    6664
    6765typedef struct {
    … …  
    256254}
    257255
    258 static hash_index_t cache_hash(unsigned long *key)
    259 {
    260         return MERGE_LOUP32(key[0], key[1]) & (CACHE_BUCKETS - 1);
    261 }
    262 
    263 static int cache_compare(unsigned long *key, hash_count_t keys, link_t *item)
     256static 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
     265static 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
     276static bool cache_match(unsigned long *key, size_t keys, const link_t *item)
    264277{
    265278        block_t *b = hash_table_get_instance(item, block_t, hash_link);
    … …  
    267280}
    268281
    269 static void cache_remove_callback(link_t *item)
    270 {
    271 }
    272 
    273 static hash_table_operations_t cache_ops = {
     282
     283static hash_table_ops_t cache_ops = {
    274284        .hash = cache_hash,
    275         .compare = cache_compare,
    276         .remove_callback = cache_remove_callback
     285        .key_hash = cache_key_hash,
     286        .match = cache_match,
     287        .equal = 0,
     288        .remove_callback = 0
    277289};
    278290
    … …  
    305317        cache->blocks_cluster = cache->lblock_size / devcon->pblock_size;
    306318
    307         if (!hash_table_create(&cache->block_hash, CACHE_BUCKETS, 2,
    308             &cache_ops)) {
     319        if (!hash_table_create(&cache->block_hash, 0, 2, &cache_ops)) {
    309320                free(cache);
    310321                return ENOMEM;
    … …  
    540551                b->lba = ba;
    541552                b->pba = ba_ltop(devcon, b->lba);
    542                 hash_table_insert(&cache->block_hash, key, &b->hash_link);
     553                hash_table_insert(&cache->block_hash, &b->hash_link);
    543554
    544555                /*

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

    r1c1da4b r0ca7286  
    3434
    3535/*
    36  * This is an implementation of generic chained hash table.
     36 * This is an implementation of a generic resizable chained hash table.
     37 *
     38 * The table grows to 2*n+1 buckets each time, starting at n == 89,
     39 * per Thomas Wang's recommendation:
     40 * http://www.concentric.net/~Ttwang/tech/hashsize.htm
     41 *
     42 * This policy produces prime table sizes for the first five resizes
     43 * and generally produces table sizes which are either prime or
     44 * have fairly large (prime/odd) divisors. Having a prime table size
     45 * mitigates the use of suboptimal hash functions and distributes
     46 * items over the whole table.
    3747 */
    3848
    … …  
    4454#include <str.h>
    4555
     56/* Optimal initial bucket count. See comment above. */
     57#define HT_MIN_BUCKETS  89
     58/* The table is resized when the average load per bucket exceeds this number. */
     59#define HT_MAX_LOAD     2
     60
     61
     62static size_t round_up_size(size_t size);
     63static bool alloc_table(size_t bucket_cnt, list_t **pbuckets);
     64static void item_inserted(hash_table_t *h);
     65static void item_removed(hash_table_t *h);
     66static inline void remove_item(hash_table_t *h, link_t *item);
     67static size_t remove_duplicates(hash_table_t *h, unsigned long key[]);
     68static size_t remove_matching(hash_table_t *h, unsigned long key[], size_t key_cnt);
     69
     70/* Dummy do nothing callback to invoke in place of remove_callback == NULL. */
     71static void nop_remove_callback(link_t *item)
     72{
     73        /* no-op */
     74}
     75
     76
    4677/** Create chained hash table.
    4778 *
    4879 * @param h        Hash table structure. Will be initialized by this call.
    49  * @param m        Number of hash table buckets.
     80 * @param init_size Initial desired number of hash table buckets. Pass zero
     81 *                 if you want the default initial size.
    5082 * @param max_keys Maximal number of keys needed to identify an item.
    51  * @param op       Hash table operations structure.
     83 * @param op       Hash table operations structure. remove_callback()
     84 *                 is optional and can be NULL if no action is to be taken
     85 *                 upon removal. equal() is optional if and only if
     86 *                 hash_table_insert_unique() will never be invoked.
     87 *                 All other operations are mandatory.
    5288 *
    5389 * @return True on success
    5490 *
    5591 */
    56 bool hash_table_create(hash_table_t *h, hash_count_t m, hash_count_t max_keys,
    57     hash_table_operations_t *op)
     92bool hash_table_create(hash_table_t *h, size_t init_size, size_t max_keys,
     93    hash_table_ops_t *op)
    5894{
    5995        assert(h);
    60         assert(op && op->hash && op->compare);
     96        assert(op && op->hash && op->key_hash && op->match);
    6197        assert(max_keys > 0);
    6298       
    63         h->entry = malloc(m * sizeof(list_t));
    64         if (!h->entry)
     99        h->bucket_cnt = round_up_size(init_size);
     100       
     101        if (!alloc_table(h->bucket_cnt, &h->bucket))
    65102                return false;
    66103       
    67         memset((void *) h->entry, 0,  m * sizeof(list_t));
    68        
    69         hash_count_t i;
    70         for (i = 0; i < m; i++)
    71                 list_initialize(&h->entry[i]);
    72        
    73         h->entries = m;
    74104        h->max_keys = max_keys;
     105        h->items = 0;
    75106        h->op = op;
    76107       
     108        if (h->op->remove_callback == 0)
     109                h->op->remove_callback = nop_remove_callback;
     110       
    77111        return true;
    78112}
    … …  
    84118void hash_table_clear(hash_table_t *h)
    85119{
    86         for (hash_count_t chain = 0; chain < h->entries; ++chain) {
    87                 link_t *cur;
    88                 link_t *next;
    89                
    90                 for (cur = h->entry[chain].head.next;
    91                     cur != &h->entry[chain].head;
    92                     cur = next) {
    93                         next = cur->next;
     120        for (size_t idx = 0; idx < h->bucket_cnt; ++idx) {
     121                list_foreach_safe(h->bucket[idx], cur, next) {
    94122                        list_remove(cur);
    95123                        h->op->remove_callback(cur);
    96124                }
    97125        }
     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        }
    98138}
    99139
    … …  
    106146{
    107147        assert(h);
    108         assert(h->entry);
    109        
    110         free(h->entry);
     148        assert(h->bucket);
     149       
     150        free(h->bucket);
     151
     152        h->bucket = 0;
     153        h->bucket_cnt = 0;
    111154}
    112155
    … …  
    117160 * @param item Item to be inserted into the hash table.
    118161 */
    119 void hash_table_insert(hash_table_t *h, unsigned long key[], link_t *item)
     162void hash_table_insert(hash_table_t *h, link_t *item)
    120163{
    121164        assert(item);
    122         assert(h && h->op && h->op->hash && h->op->compare);
    123        
    124         hash_index_t chain = h->op->hash(key);
    125         assert(chain < h->entries);
    126        
    127         list_append(item, &h->entry[chain]);
     165        assert(h && h->bucket);
     166        assert(h->op && h->op->hash);
     167       
     168        size_t idx = h->op->hash(item) % h->bucket_cnt;
     169       
     170        assert(idx < h->bucket_cnt);
     171       
     172        list_append(item, &h->bucket[idx]);
     173        item_inserted(h);
     174}
     175
     176
     177/** Insert item into a hash table if not already present.
     178 *
     179 * @param h    Hash table.
     180 * @param key  Array of all keys necessary to compute hash index.
     181 * @param item Item to be inserted into the hash table.
     182 *
     183 * @return False if such an item had already been inserted.
     184 * @return True if the inserted item was the only item with such a lookup key.
     185 */
     186bool hash_table_insert_unique(hash_table_t *h, link_t *item)
     187{
     188        assert(item);
     189        assert(h && h->bucket && h->bucket_cnt);
     190        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);
     196       
     197        /* Check for duplicates. */
     198        list_foreach(h->bucket[idx], cur) {
     199                /*
     200                 * We could filter out items using their hashes first, but
     201                 * calling equal() might very well be just as fast.
     202                 */
     203                if (h->op->equal(cur, item))
     204                        return false;
     205        }
     206       
     207        list_append(item, &h->bucket[idx]);
     208        item_inserted(h);
     209       
     210        return true;
    128211}
    129212
    … …  
    138221link_t *hash_table_find(hash_table_t *h, unsigned long key[])
    139222{
    140         assert(h && h->op && h->op->hash && h->op->compare);
    141        
    142         hash_index_t chain = h->op->hash(key);
    143         assert(chain < h->entries);
    144        
    145         list_foreach(h->entry[chain], cur) {
    146                 if (h->op->compare(key, h->max_keys, cur)) {
    147                         /*
    148                          * The entry is there.
     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       
     231        list_foreach(h->bucket[idx], cur) {
     232                /*
     233                 * 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
     235                 * just as fast as op->hash().
     236                 */
     237                if (h->op->match(key, h->max_keys, cur)) {
     238                        return cur;
     239                }
     240        }
     241       
     242        return NULL;
     243}
     244
     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 */
     255void 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!).
    149262                         */
    150                         return cur;
    151                 }
    152         }
    153        
    154         return NULL;
     263                        if (!f(cur, arg))
     264                                return;
     265                }
     266        }
    155267}
    156268
    … …  
    163275 *             the hash table.
    164276 * @param keys Number of keys in the 'key' array.
    165  *
    166  */
    167 void hash_table_remove(hash_table_t *h, unsigned long key[], hash_count_t keys)
    168 {
    169         assert(h && h->op && h->op->hash && h->op->compare &&
     277 *
     278 * @return Returns the number of removed items.
     279 */
     280size_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 &&
    170284            h->op->remove_callback);
    171         assert(keys <= h->max_keys);
    172        
    173         if (keys == h->max_keys) {
     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 {
    174291                /*
    175                  * All keys are known, hash_table_find() can be used to find the
    176                  * entry.
    177                  */
    178                
    179                 link_t *cur = hash_table_find(h, key);
    180                 if (cur) {
    181                         list_remove(cur);
    182                         h->op->remove_callback(cur);
    183                 }
    184                
    185                 return;
    186         }
    187        
     292                * Fewer keys were passed.
     293                * Any partially matching entries are to be removed.
     294                */
     295                return remove_matching(h, key, key_cnt);
     296        }
     297}
     298
     299/** Removes an item already present in the table. The item must be in the table.*/
     300void hash_table_remove_item(hash_table_t *h, link_t *item)
     301{
     302        assert(item);
     303        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. */
     309static inline void remove_item(hash_table_t *h, link_t *item)
     310{
     311        assert(item);
     312       
     313        list_remove(item);
     314        item_removed(h);
     315        h->op->remove_callback(item);
     316}
     317
     318/** Removes all items matching key in the bucket key hashes to. */
     319static 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. */
     342static 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;
    188349        /*
    189350         * Fewer keys were passed.
    190351         * Any partially matching entries are to be removed.
    191352         */
    192         hash_index_t chain;
    193         for (chain = 0; chain < h->entries; chain++) {
    194                 for (link_t *cur = h->entry[chain].head.next;
    195                     cur != &h->entry[chain].head;
    196                     cur = cur->next) {
    197                         if (h->op->compare(key, keys, cur)) {
    198                                 link_t *hlp;
    199                                
    200                                 hlp = cur;
    201                                 cur = cur->prev;
    202                                
    203                                 list_remove(hlp);
    204                                 h->op->remove_callback(hlp);
    205                                
    206                                 continue;
     353        for (size_t idx = 0; idx < h->bucket_cnt; ++idx) {
     354                list_foreach_safe(h->bucket[idx], cur, next) {
     355                        if (h->op->match(key, key_cnt, cur)) {
     356                                ++removed;
     357                                remove_item(h, cur);
    207358                        }
    208359                }
    209360        }
    210 }
    211 
    212 /** Apply function to all items in hash table.
    213  *
    214  * @param h   Hash table.
    215  * @param f   Function to be applied.
    216  * @param arg Argument to be passed to the function.
    217  *
    218  */
    219 void hash_table_apply(hash_table_t *h, void (*f)(link_t *, void *), void *arg)
    220 {       
    221         for (hash_index_t bucket = 0; bucket < h->entries; bucket++) {
    222                 link_t *cur;
    223                 link_t *next;
    224 
    225                 for (cur = h->entry[bucket].head.next; cur != &h->entry[bucket].head;
    226                     cur = next) {
    227                         /*
    228                          * The next pointer must be stored prior to the functor
    229                          * call to allow using destructor as the functor (the
    230                          * free function could overwrite the cur->next pointer).
    231                          */
    232                         next = cur->next;
    233                         f(cur, arg);
    234                 }
    235         }
    236 }
     361       
     362        return removed;
     363       
     364}
     365
     366/** Rounds up size to the nearest suitable table size. */
     367static size_t round_up_size(size_t size)
     368{
     369        size_t rounded_size = HT_MIN_BUCKETS;
     370       
     371        while (rounded_size < size) {
     372                rounded_size = 2 * rounded_size + 1;
     373        }
     374       
     375        return rounded_size;
     376}
     377
     378/** Allocates and initializes the desired number of buckets. True if successful.*/
     379static bool alloc_table(size_t bucket_cnt, list_t **pbuckets)
     380{
     381        assert(pbuckets && HT_MIN_BUCKETS <= bucket_cnt);
     382               
     383        list_t *buckets = malloc(bucket_cnt * sizeof(list_t));
     384        if (!buckets)
     385                return false;
     386       
     387        for (size_t i = 0; i < bucket_cnt; i++)
     388                list_initialize(&buckets[i]);
     389
     390        *pbuckets = buckets;
     391        return true;
     392}
     393
     394/** Allocates and rehashes items to a new table. Frees the old table. */
     395static 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. */
     420static 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) {
     425                /*
     426                 * Keep the bucket_cnt odd (possibly also prime).
     427                 * Shrink from 2n + 1 to n. Integer division discards the +1.
     428                 */
     429                size_t new_bucket_cnt = h->bucket_cnt / 2;
     430                resize(h, new_bucket_cnt);
     431        }
     432}
     433
     434/** Grows the table if needed. */
     435static void item_inserted(hash_table_t *h)
     436{
     437        ++h->items;
     438       
     439        /* Grow the table if the average bucket load exceeds the maximum. */
     440        if (HT_MAX_LOAD * h->bucket_cnt < h->items) {
     441                /* Keep the bucket_cnt odd (possibly also prime). */
     442                size_t new_bucket_cnt = 2 * h->bucket_cnt + 1;
     443                resize(h, new_bucket_cnt);
     444        }
     445}
     446
    237447
    238448/** @}

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

    r1c1da4b r0ca7286  
    115115#include <macros.h>
    116116
    117 #define CLIENT_HASH_TABLE_BUCKETS  32
    118 #define CONN_HASH_TABLE_BUCKETS    32
    119117
    120118/** Session data */
    … …  
    392390static LIST_INITIALIZE(timeout_list);
    393391
    394 static hash_index_t client_hash(unsigned long key[])
     392static size_t client_key_hash(unsigned long key[])
    395393{
    396394        assert(key);
    397        
    398         return (((key[0]) >> 4) % CLIENT_HASH_TABLE_BUCKETS);
    399 }
    400 
    401 static int client_compare(unsigned long key[], hash_count_t keys, link_t *item)
     395        /* LOWER32(in_task_id) */
     396        return key[0] >> 4;
     397}
     398
     399static 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
     411static bool client_match(unsigned long key[], size_t keys, const link_t *item)
    402412{
    403413        assert(key);
    … …  
    410420}
    411421
    412 static void client_remove(link_t *item)
    413 {
    414 }
    415422
    416423/** Operations for the client hash table. */
    417 static hash_table_operations_t client_hash_table_ops = {
     424static hash_table_ops_t client_hash_table_ops = {
    418425        .hash = client_hash,
    419         .compare = client_compare,
    420         .remove_callback = client_remove
     426        .key_hash = client_key_hash,
     427        .match = client_match,
     428        .equal = 0,
     429        .remove_callback = 0
    421430};
    422431
    … …  
    428437 *
    429438 */
    430 static hash_index_t conn_hash(unsigned long key[])
     439static size_t conn_key_hash(unsigned long key[])
    431440{
    432441        assert(key);
    433        
    434         return (((key[0]) >> 4) % CONN_HASH_TABLE_BUCKETS);
     442        return key[0] >> 4;
     443}
     444
     445static 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);
    435450}
    436451
    … …  
    444459 *
    445460 */
    446 static int conn_compare(unsigned long key[], hash_count_t keys, link_t *item)
     461static bool conn_match(unsigned long key[], size_t keys, const link_t *item)
    447462{
    448463        assert(key);
    … …  
    453468}
    454469
     470static 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
    455478static void conn_remove(link_t *item)
    456479{
    … …  
    458481
    459482/** Operations for the connection hash table. */
    460 static hash_table_operations_t conn_hash_table_ops = {
     483static hash_table_ops_t conn_hash_table_ops = {
    461484        .hash = conn_hash,
    462         .compare = conn_compare,
     485        .key_hash = conn_key_hash,
     486        .match = conn_match,
     487        .equal = conn_equal,
    463488        .remove_callback = conn_remove
    464489};
    … …  
    715740               
    716741                        atomic_set(&client->refcnt, 1);
    717                         hash_table_insert(&client_hash_table, key, &client->link);
     742                        hash_table_insert(&client_hash_table, &client->link);
    718743                }
    719744        }
    … …  
    915940       
    916941        /* Add connection to the connection hash table */
    917         unsigned long key = conn->in_phone_hash;
    918942       
    919943        futex_down(&async_futex);
    920         hash_table_insert(&conn_hash_table, &key, &conn->link);
     944        hash_table_insert(&conn_hash_table, &conn->link);
    921945        futex_up(&async_futex);
    922946       
    … …  
    11101134void __async_init(void)
    11111135{
    1112         if (!hash_table_create(&client_hash_table, CLIENT_HASH_TABLE_BUCKETS,
    1113             2, &client_hash_table_ops))
     1136        if (!hash_table_create(&client_hash_table, 0, 2, &client_hash_table_ops))
    11141137                abort();
    11151138       
    1116         if (!hash_table_create(&conn_hash_table, CONN_HASH_TABLE_BUCKETS,
    1117             1, &conn_hash_table_ops))
     1139        if (!hash_table_create(&conn_hash_table, 0, 1, &conn_hash_table_ops))
    11181140                abort();
    11191141       

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

    r1c1da4b r0ca7286  
    4040#include <bool.h>
    4141
    42 typedef unsigned long hash_count_t;
    43 typedef unsigned long hash_index_t;
    4442
    4543/** Set of operations for hash table. */
    4644typedef struct {
    47         /** Hash function.
    48          *
    49          * @param key Array of keys needed to compute hash index.
    50          *            All keys must be passed.
    51          *
    52          * @return Index into hash table.
    53          *
     45        /** Returns the hash of the key stored in the item.
    5446         */
    55         hash_index_t (*hash)(unsigned long key[]);
     47        size_t (*hash)(const link_t *item);
    5648       
    57         /** Hash table item comparison function.
     49        /** Returns the hash of the key.
     50         */
     51        size_t (*key_hash)(unsigned long key[]);
     52       
     53        /** Hash table item match function.
    5854         *
    5955         * @param key Array of keys that will be compared with item. It is
    … …  
    6359         *
    6460         */
    65         int (*compare)(unsigned long key[], hash_count_t keys, link_t *item);
     61        bool (*match)(unsigned long key[], size_t keys, const link_t *item);
     62
     63        /**
     64         */
     65        bool (*equal)(const link_t *item1, const link_t *item2);
    6666       
    6767        /** Hash table item removal callback.
     68         *
     69         * Must not invoke any mutating functions of the hash table.
    6870         *
    6971         * @param item Item that was removed from the hash table.
    70          *
    7172         */
    7273        void (*remove_callback)(link_t *item);
    73 } hash_table_operations_t;
     74} hash_table_ops_t;
    7475
    7576/** Hash table structure. */
    7677typedef struct {
    77         list_t *entry;
    78         hash_count_t entries;
    79         hash_count_t max_keys;
    80         hash_table_operations_t *op;
     78        list_t *bucket;
     79        size_t bucket_cnt;
     80        size_t max_keys;
     81        size_t items;
     82        hash_table_ops_t *op;
    8183} hash_table_t;
    8284
    … …  
    8486    list_get_instance((item), type, member)
    8587
    86 extern bool hash_table_create(hash_table_t *, hash_count_t, hash_count_t,
    87     hash_table_operations_t *);
     88extern bool hash_table_create(hash_table_t *, size_t, size_t,
     89        hash_table_ops_t *);
    8890extern void hash_table_clear(hash_table_t *);
    89 extern void hash_table_insert(hash_table_t *, unsigned long [], link_t *);
     91extern void hash_table_insert(hash_table_t *, link_t *);
     92extern bool hash_table_insert_unique(hash_table_t *, link_t *);
    9093extern link_t *hash_table_find(hash_table_t *, unsigned long []);
    91 extern void hash_table_remove(hash_table_t *, unsigned long [], hash_count_t);
     94extern size_t hash_table_remove(hash_table_t *, unsigned long [], size_t);
     95extern void hash_table_remove_item(hash_table_t *, link_t *);
    9296extern void hash_table_destroy(hash_table_t *);
    93 extern void hash_table_apply(hash_table_t *, void (*)(link_t *, void *),
    94     void *);
     97extern void hash_table_apply(hash_table_t *, bool (*)(link_t *, void *),
     98        void *);
    9599
    96100#endif

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

    r1c1da4b r0ca7286  
    7171            iterator != &(list).head; iterator = iterator->next)
    7272
     73/** Unlike list_foreach(), allows removing items while traversing a list.
     74 *
     75 * @code
     76 * list_t mylist;
     77 * typedef struct item {
     78 *     int value;
     79 *     link_t item_link;
     80 * } item_t;
     81 *
     82 * //..
     83 *
     84 * // Print each list element's value and remove the element from the list.
     85 * list_foreach_safe(mylist, cur_link, next_link) {
     86 *     item_t *cur_item = list_get_instance(cur_link, item_t, item_link);
     87 *     printf("%d\n", cur_item->value);
     88 *     list_remove(cur_link);
     89 * }
     90 * @endcode
     91 *
     92 * @param list List to traverse.
     93 * @param iterator Iterator to the current element of the list.
     94 *             The item this iterator points may be safely removed
     95 *             from the list.
     96 * @param next_iter Iterator to the next element of the list.
     97 */
     98#define list_foreach_safe(list, iterator, next_iter) \
     99        for (link_t *iterator = (list).head.next, \
     100                *next_iter = iterator->next; \
     101                iterator != &(list).head; \
     102                iterator = next_iter, next_iter = iterator->next)
     103
     104
    73105#define assert_link_not_used(link) \
    74106        assert(((link)->prev == NULL) && ((link)->next == NULL))

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

    r1c1da4b r0ca7286  
    5151         * Operations for table
    5252         */
    53         hash_table_operations_t table_operations;
     53        hash_table_ops_t table_operations;
    5454        /**
    5555         * WOL virtues hashed by their ID's.

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

    r1c1da4b r0ca7286  
    4040#include <errno.h>
    4141
    42 #define NIC_WV_HASH_COUNT 32
    43 
    44 /**
    45  * Hash table helper function
    46  */
    47 static int nic_wv_compare(unsigned long key[], hash_count_t keys,
    48         link_t *item)
     42
     43/*
     44 * Hash table helper functions
     45 */
     46
     47static size_t nic_wv_key_hash(unsigned long keys[])
     48{
     49        return keys[0];
     50}
     51
     52static size_t nic_wv_hash(const link_t *item)
     53{
     54        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
     59static bool nic_wv_match(unsigned long key[], size_t keys, const link_t *item)
    4960{
    5061        nic_wol_virtue_t *virtue = (nic_wol_virtue_t *) item;
    … …  
    5364
    5465/**
    55  * Hash table helper function
    56  */
    57 static void nic_wv_rc(link_t *item)
    58 {
    59 }
    60 
    61 /**
    62  * Hash table helper function
    63  */
    64 static hash_index_t nic_wv_hash(unsigned long keys[])
    65 {
    66         return keys[0] % NIC_WV_HASH_COUNT;
    67 }
    68 
    69 /**
    7066 * Initializes the WOL virtues structure
    7167 *
    … …  
    7773int nic_wol_virtues_init(nic_wol_virtues_t *wvs)
    7874{
    79         bzero(wvs, sizeof (nic_wol_virtues_t));
    80         wvs->table_operations.compare = nic_wv_compare;
     75        bzero(wvs, sizeof(nic_wol_virtues_t));
    8176        wvs->table_operations.hash = nic_wv_hash;
    82         wvs->table_operations.remove_callback = nic_wv_rc;
    83         if (!hash_table_create(&wvs->table, NIC_WV_HASH_COUNT, 1,
    84                 &wvs->table_operations)) {
     77        wvs->table_operations.key_hash = nic_wv_key_hash;
     78        wvs->table_operations.match = nic_wv_match;
     79        wvs->table_operations.equal = 0;
     80        wvs->table_operations.remove_callback = 0;
     81       
     82        if (!hash_table_create(&wvs->table, 0, 1, &wvs->table_operations)) {
    8583                return ENOMEM;
    8684        }
    … …  
    172170        } while (NULL !=
    173171                hash_table_find(&wvs->table, (unsigned long *) &virtue->id));
    174         hash_table_insert(&wvs->table,
    175                 (unsigned long *) &virtue->id, &virtue->item);
     172        hash_table_insert(&wvs->table, &virtue->item);
    176173        virtue->next = wvs->lists[virtue->type];
    177174        wvs->lists[virtue->type] = virtue;

  • uspace/srv/devman/devman.c

    r1c1da4b r0ca7286  
    6666/* hash table operations */
    6767
    68 static hash_index_t devices_hash(unsigned long key[])
    69 {
    70         return key[0] % DEVICE_BUCKETS;
    71 }
    72 
    73 static int devman_devices_compare(unsigned long key[], hash_count_t keys,
    74     link_t *item)
     68static size_t devices_key_hash(unsigned long key[])
     69{
     70        return key[0];
     71}
     72
     73static 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
     80static 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
     87static 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
     94static bool devman_devices_match(unsigned long key[], size_t keys,
     95    const link_t *item)
    7596{
    7697        dev_node_t *dev = hash_table_get_instance(item, dev_node_t, devman_dev);
    … …  
    7899}
    79100
    80 static int devman_functions_compare(unsigned long key[], hash_count_t keys,
    81     link_t *item)
     101static bool devman_functions_match(unsigned long key[], size_t keys,
     102    const link_t *item)
    82103{
    83104        fun_node_t *fun = hash_table_get_instance(item, fun_node_t, devman_fun);
    … …  
    85106}
    86107
    87 static int loc_functions_compare(unsigned long key[], hash_count_t keys,
    88     link_t *item)
     108static bool loc_functions_match(unsigned long key[], size_t keys,
     109    const link_t *item)
    89110{
    90111        fun_node_t *fun = hash_table_get_instance(item, fun_node_t, loc_fun);
    … …  
    92113}
    93114
    94 static void devices_remove_callback(link_t *item)
    95 {
    96 }
    97 
    98 static hash_table_operations_t devman_devices_ops = {
    99         .hash = devices_hash,
    100         .compare = devman_devices_compare,
    101         .remove_callback = devices_remove_callback
     115
     116static hash_table_ops_t devman_devices_ops = {
     117        .hash = devman_devices_hash,
     118        .key_hash = devices_key_hash,
     119        .match = devman_devices_match,
     120        .equal = 0,
     121        .remove_callback = 0
    102122};
    103123
    104 static hash_table_operations_t devman_functions_ops = {
    105         .hash = devices_hash,
    106         .compare = devman_functions_compare,
    107         .remove_callback = devices_remove_callback
     124static hash_table_ops_t devman_functions_ops = {
     125        .hash = devman_functions_hash,
     126        .key_hash = devices_key_hash,
     127        .match = devman_functions_match,
     128        .equal = 0,
     129        .remove_callback = 0
    108130};
    109131
    110 static hash_table_operations_t loc_devices_ops = {
    111         .hash = devices_hash,
    112         .compare = loc_functions_compare,
    113         .remove_callback = devices_remove_callback
     132static hash_table_ops_t loc_devices_ops = {
     133        .hash = loc_functions_hash,
     134        .key_hash = devices_key_hash,
     135        .match = loc_functions_match,
     136        .equal = 0,
     137        .remove_callback = 0
    114138};
    115139
    … …  
    974998        tree->current_handle = 0;
    975999       
    976         hash_table_create(&tree->devman_devices, DEVICE_BUCKETS, 1,
    977             &devman_devices_ops);
    978         hash_table_create(&tree->devman_functions, DEVICE_BUCKETS, 1,
    979             &devman_functions_ops);
    980         hash_table_create(&tree->loc_functions, DEVICE_BUCKETS, 1,
    981             &loc_devices_ops);
     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);
    9821003       
    9831004        fibril_rwlock_initialize(&tree->rwlock);
    … …  
    12821303        /* Add the node to the handle-to-node map. */
    12831304        dev->handle = ++tree->current_handle;
    1284         unsigned long key = dev->handle;
    1285         hash_table_insert(&tree->devman_devices, &key, &dev->devman_dev);
     1305        hash_table_insert(&tree->devman_devices, &dev->devman_dev);
    12861306
    12871307        /* Add the node to the list of its parent's children. */
    … …  
    13461366        /* Add the node to the handle-to-node map. */
    13471367        fun->handle = ++tree->current_handle;
    1348         unsigned long key = fun->handle;
    1349         hash_table_insert(&tree->devman_functions, &key, &fun->devman_fun);
     1368        hash_table_insert(&tree->devman_functions, &fun->devman_fun);
    13501369
    13511370        /* Add the node to the list of its parent's children. */
    … …  
    14991518        assert(fibril_rwlock_is_write_locked(&tree->rwlock));
    15001519       
    1501         unsigned long key = (unsigned long) fun->service_id;
    1502         hash_table_insert(&tree->loc_functions, &key, &fun->loc_fun);
     1520        hash_table_insert(&tree->loc_functions, &fun->loc_fun);
    15031521}
    15041522

  • uspace/srv/devman/devman.h

    r1c1da4b r0ca7286  
    5252
    5353#define MATCH_EXT ".ma"
    54 #define DEVICE_BUCKETS 256
    5554
    5655#define LOC_DEVICE_NAMESPACE "devices"

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

    r1c1da4b r0ca7286  
    6363#define NODE_CACHE_SIZE  200
    6464
    65 #define NODES_BUCKETS  256
    66 
    6765#define NODES_KEY_SRVC   0
    6866#define NODES_KEY_INDEX  1
    … …  
    226224static hash_table_t nodes;
    227225
    228 static hash_index_t nodes_hash(unsigned long key[])
    229 {
    230         return key[NODES_KEY_INDEX] % NODES_BUCKETS;
    231 }
    232 
    233 static int nodes_compare(unsigned long key[], hash_count_t keys, link_t *item)
    234 {
    235         cdfs_node_t *node =
    236             hash_table_get_instance(item, cdfs_node_t, nh_link);
    237        
    238         switch (keys) {
    239         case 1:
     226static size_t nodes_key_hash(unsigned long key[])
     227{
     228        return key[NODES_KEY_INDEX];
     229}
     230
     231static 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
     242static 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) {
    240247                return (node->service_id == key[NODES_KEY_SRVC]);
    241         case 2:
     248        } else {
     249                assert(keys == 2);
    242250                return ((node->service_id == key[NODES_KEY_SRVC]) &&
    243251                    (node->index == key[NODES_KEY_INDEX]));
    244         default:
    245                 assert((keys == 1) || (keys == 2));
    246         }
    247        
    248         return 0;
     252        }
     253}
     254
     255static 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;
    249262}
    250263
    251264static void nodes_remove_callback(link_t *item)
    252265{
    253         cdfs_node_t *node =
    254             hash_table_get_instance(item, cdfs_node_t, nh_link);
     266        cdfs_node_t *node = hash_table_get_instance(item, cdfs_node_t, nh_link);
    255267       
    256268        assert(node->type == CDFS_DIRECTORY);
    … …  
    268280
    269281/** Nodes hash table operations */
    270 static hash_table_operations_t nodes_ops = {
     282static hash_table_ops_t nodes_ops = {
    271283        .hash = nodes_hash,
    272         .compare = nodes_compare,
     284        .key_hash = nodes_key_hash,
     285        .match = nodes_match,
     286        .equal = nodes_equal,
    273287        .remove_callback = nodes_remove_callback
    274288};
    … …  
    353367       
    354368        /* Insert the new node into the nodes hash table. */
    355         unsigned long key[] = {
    356                 [NODES_KEY_SRVC] = node->service_id,
    357                 [NODES_KEY_INDEX] = node->index
    358         };
    359        
    360         hash_table_insert(&nodes, key, &node->nh_link);
     369        hash_table_insert(&nodes, &node->nh_link);
    361370       
    362371        *rfn = FS_NODE(node);
    … …  
    912921}
    913922
     923static bool cache_remove_closed(link_t *item, void *arg)
     924{
     925        size_t *premove_cnt = (size_t*)arg;
     926       
     927        /* Some nodes were requested to be removed from the cache. */
     928        if (0 < *premove_cnt) {
     929                cdfs_node_t *node =     hash_table_get_instance(item, cdfs_node_t, nh_link);
     930
     931                if (!node->opened) {
     932                        hash_table_remove_item(&nodes, item);
     933                       
     934                        --nodes_cached;
     935                        --*premove_cnt;
     936                }
     937        }
     938       
     939        /* Only continue if more nodes were requested to be removed. */
     940        return 0 < *premove_cnt;
     941}
     942
    914943static void cleanup_cache(service_id_t service_id)
    915944{
    916945        if (nodes_cached > NODE_CACHE_SIZE) {
    917                 size_t remove = nodes_cached - NODE_CACHE_SIZE;
    918                
    919                 // FIXME: this accesses the internals of the hash table
    920                 //        and should be rewritten in a clean way
    921                
    922                 for (hash_index_t chain = 0; chain < nodes.entries; chain++) {
    923                         for (link_t *link = nodes.entry[chain].head.next;
    924                             link != &nodes.entry[chain].head;
    925                             link = link->next) {
    926                                 if (remove == 0)
    927                                         return;
    928                                
    929                                 cdfs_node_t *node =
    930                                     hash_table_get_instance(link, cdfs_node_t, nh_link);
    931                                 if (node->opened == 0) {
    932                                         link_t *tmp = link;
    933                                         link = link->prev;
    934                                        
    935                                         list_remove(tmp);
    936                                         nodes.op->remove_callback(tmp);
    937                                         nodes_cached--;
    938                                         remove--;
    939                                        
    940                                         continue;
    941                                 }
    942                         }
    943                 }
     946                size_t remove_cnt = nodes_cached - NODE_CACHE_SIZE;
     947               
     948                if (0 < remove_cnt)
     949                        hash_table_apply(&nodes, cache_remove_closed, &remove_cnt);
    944950        }
    945951}
    … …  
    10071013bool cdfs_init(void)
    10081014{
    1009         if (!hash_table_create(&nodes, NODES_BUCKETS, 2, &nodes_ops))
     1015        if (!hash_table_create(&nodes, 0, 2, &nodes_ops))
    10101016                return false;
    10111017       

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

    r1c1da4b r0ca7286  
    112112static hash_table_t up_hash;
    113113
    114 #define UPH_BUCKETS_LOG 12
    115 #define UPH_BUCKETS     (1 << UPH_BUCKETS_LOG)
    116 
    117114#define UPH_SID_KEY     0
    118115#define UPH_PFC_KEY     1
    119116#define UPH_PDI_KEY     2
    120117
    121 static hash_index_t pos_hash(unsigned long key[])
    122 {
    123         service_id_t service_id = (service_id_t)key[UPH_SID_KEY];
    124         exfat_cluster_t pfc = (exfat_cluster_t)key[UPH_PFC_KEY];
    125         unsigned pdi = (unsigned)key[UPH_PDI_KEY];
    126 
    127         hash_index_t h;
    128 
    129         /*
    130          * The least significant half of all bits are the least significant bits
    131          * of the parent node's first cluster.
    132          *
    133          * The least significant half of the most significant half of all bits
    134          * are the least significant bits of the node's dentry index within the
    135          * parent directory node.
    136          *
    137          * The most significant half of the most significant half of all bits
    138          * are the least significant bits of the device handle.
    139          */
    140         h = pfc & ((1 << (UPH_BUCKETS_LOG / 2)) - 1);
    141         h |= (pdi & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) <<
    142             (UPH_BUCKETS_LOG / 2);
    143         h |= (service_id & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) <<
    144             (3 * (UPH_BUCKETS_LOG / 4));
    145 
    146         return h;
    147 }
    148 
    149 static int pos_compare(unsigned long key[], hash_count_t keys, link_t *item)
     118static 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
     130static 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
     143static bool pos_match(unsigned long key[], size_t keys, const link_t *item)
    150144{
    151145        service_id_t service_id = (service_id_t)key[UPH_SID_KEY];
    … …  
    169163}
    170164
    171 static void pos_remove_callback(link_t *item)
    172 {
    173         /* nothing to do */
    174 }
    175 
    176 static hash_table_operations_t uph_ops = {
     165static hash_table_ops_t uph_ops = {
    177166        .hash = pos_hash,
    178         .compare = pos_compare,
    179         .remove_callback = pos_remove_callback,
     167        .key_hash = pos_key_hash,
     168        .match = pos_match,
     169        .equal = 0,
     170        .remove_callback = 0,
    180171};
    181172
    … …  
    186177static hash_table_t ui_hash;
    187178
    188 #define UIH_BUCKETS_LOG 12
    189 #define UIH_BUCKETS     (1 << UIH_BUCKETS_LOG)
    190 
    191179#define UIH_SID_KEY     0
    192180#define UIH_INDEX_KEY   1
    193181
    194 static hash_index_t idx_hash(unsigned long key[])
     182static size_t idx_key_hash(unsigned long key[])
    195183{
    196184        service_id_t service_id = (service_id_t)key[UIH_SID_KEY];
    197185        fs_index_t index = (fs_index_t)key[UIH_INDEX_KEY];
    198186
    199         hash_index_t h;
    200 
    201         h = service_id & ((1 << (UIH_BUCKETS_LOG / 2)) - 1);
    202         h |= (index & ((1 << (UIH_BUCKETS_LOG / 2)) - 1)) <<
    203             (UIH_BUCKETS_LOG / 2);
    204 
    205         return h;
    206 }
    207 
    208 static int idx_compare(unsigned long key[], hash_count_t keys, link_t *item)
     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
     197static 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
     209static bool idx_match(unsigned long key[], size_t keys, const link_t *item)
    209210{
    210211        service_id_t service_id = (service_id_t)key[UIH_SID_KEY];
    … …  
    233234}
    234235
    235 static hash_table_operations_t uih_ops = {
     236static hash_table_ops_t uih_ops = {
    236237        .hash = idx_hash,
    237         .compare = idx_compare,
     238        .key_hash = idx_key_hash,
     239        .match = idx_match,
     240        .equal = 0,
    238241        .remove_callback = idx_remove_callback,
    239242};
    … …  
    400403        }
    401404               
    402         unsigned long ikey[] = {
    403                 [UIH_SID_KEY] = service_id,
    404                 [UIH_INDEX_KEY] = fidx->index,
    405         };
    406        
    407         hash_table_insert(&ui_hash, ikey, &fidx->uih_link);
     405        hash_table_insert(&ui_hash, &fidx->uih_link);
    408406        fibril_mutex_lock(&fidx->lock);
    409407        fibril_mutex_unlock(&used_lock);
    … …  
    437435                }
    438436               
    439                 unsigned long ikey[] = {
    440                         [UIH_SID_KEY] = service_id,
    441                         [UIH_INDEX_KEY] = fidx->index,
    442                 };
    443        
    444437                fidx->pfc = pfc;
    445438                fidx->pdi = pdi;
    446439
    447                 hash_table_insert(&up_hash, pkey, &fidx->uph_link);
    448                 hash_table_insert(&ui_hash, ikey, &fidx->uih_link);
     440                hash_table_insert(&up_hash, &fidx->uph_link);
     441                hash_table_insert(&ui_hash, &fidx->uih_link);
    449442        }
    450443        fibril_mutex_lock(&fidx->lock);
    … …  
    456449void exfat_idx_hashin(exfat_idx_t *idx)
    457450{
    458         unsigned long pkey[] = {
    459                 [UPH_SID_KEY] = idx->service_id,
    460                 [UPH_PFC_KEY] = idx->pfc,
    461                 [UPH_PDI_KEY] = idx->pdi,
    462         };
    463 
    464         fibril_mutex_lock(&used_lock);
    465         hash_table_insert(&up_hash, pkey, &idx->uph_link);
     451        fibril_mutex_lock(&used_lock);
     452        hash_table_insert(&up_hash, &idx->uph_link);
    466453        fibril_mutex_unlock(&used_lock);
    467454}
    … …  
    532519int exfat_idx_init(void)
    533520{
    534         if (!hash_table_create(&up_hash, UPH_BUCKETS, 3, &uph_ops))
     521        if (!hash_table_create(&up_hash, 0, 3, &uph_ops))
    535522                return ENOMEM;
    536         if (!hash_table_create(&ui_hash, UIH_BUCKETS, 2, &uih_ops)) {
     523        if (!hash_table_create(&ui_hash, 0, 2, &uih_ops)) {
    537524                hash_table_destroy(&up_hash);
    538525                return ENOMEM;

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

    r1c1da4b r0ca7286  
    6565#define OPEN_NODES_DEV_HANDLE_KEY 0
    6666#define OPEN_NODES_INODE_KEY 1
    67 #define OPEN_NODES_BUCKETS 256
    6867
    6968typedef struct ext2fs_instance {
    … …  
    123122
    124123/* Hash table interface for open nodes hash table */
    125 static hash_index_t open_nodes_hash(unsigned long key[])
    126 {
    127         /* TODO: This is very simple and probably can be improved */
    128         return key[OPEN_NODES_INODE_KEY] % OPEN_NODES_BUCKETS;
    129 }
    130 
    131 static int open_nodes_compare(unsigned long key[], hash_count_t keys,
    132     link_t *item)
     124static 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
     133static size_t open_nodes_hash(const link_t *item)
     134{
     135        ext2fs_node_t *enode = hash_table_get_instance(item, ext2fs_node_t, link);
     136
     137        assert(enode->instance);
     138        assert(enode->inode_ref);
     139       
     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
     148static bool open_nodes_match(unsigned long key[], size_t keys,
     149    const link_t *item)
    133150{
    134151        ext2fs_node_t *enode = hash_table_get_instance(item, ext2fs_node_t, link);
    … …  
    145162}
    146163
    147 static void open_nodes_remove_cb(link_t *link)
    148 {
    149         /* We don't use remove callback for this hash table */
    150 }
    151 
    152 static hash_table_operations_t open_nodes_ops = {
     164static hash_table_ops_t open_nodes_ops = {
    153165        .hash = open_nodes_hash,
    154         .compare = open_nodes_compare,
    155         .remove_callback = open_nodes_remove_cb,
     166        .key_hash = open_nodes_key_hash,
     167        .match = open_nodes_match,
     168        .equal = 0,
     169        .remove_callback = 0,
    156170};
    157171
    … …  
    161175int ext2fs_global_init(void)
    162176{
    163         if (!hash_table_create(&open_nodes, OPEN_NODES_BUCKETS,
    164             OPEN_NODES_KEYS, &open_nodes_ops)) {
     177        if (!hash_table_create(&open_nodes, 0, OPEN_NODES_KEYS, &open_nodes_ops)) {
    165178                return ENOMEM;
    166179        }
    … …  
    362375        *rfn = node;
    363376       
    364         hash_table_insert(&open_nodes, key, &enode->link);
     377        hash_table_insert(&open_nodes, &enode->link);
    365378        inst->open_nodes_count++;
    366379       

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

    r1c1da4b r0ca7286  
    4646#include <malloc.h>
    4747
     48
    4849/** Each instance of this type describes one interval of freed VFS indices. */
    4950typedef struct {
    … …  
    113114static hash_table_t up_hash;
    114115
    115 #define UPH_BUCKETS_LOG 12
    116 #define UPH_BUCKETS     (1 << UPH_BUCKETS_LOG)
    117 
    118116#define UPH_SID_KEY     0
    119117#define UPH_PFC_KEY     1
    120118#define UPH_PDI_KEY     2
    121119
    122 static hash_index_t pos_hash(unsigned long key[])
    123 {
    124         service_id_t service_id = (service_id_t)key[UPH_SID_KEY];
    125         fat_cluster_t pfc = (fat_cluster_t)key[UPH_PFC_KEY];
    126         unsigned pdi = (unsigned)key[UPH_PDI_KEY];
    127 
    128         hash_index_t h;
    129 
    130         /*
    131          * The least significant half of all bits are the least significant bits
    132          * of the parent node's first cluster.
    133          *
    134          * The least significant half of the most significant half of all bits
    135          * are the least significant bits of the node's dentry index within the
    136          * parent directory node.
    137          *
    138          * The most significant half of the most significant half of all bits
    139          * are the least significant bits of the device handle.
    140          */
    141         h = pfc & ((1 << (UPH_BUCKETS_LOG / 2)) - 1);
    142         h |= (pdi & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) <<
    143             (UPH_BUCKETS_LOG / 2);
    144         h |= (service_id & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) <<
    145             (3 * (UPH_BUCKETS_LOG / 4));
    146 
    147         return h;
    148 }
    149 
    150 static int pos_compare(unsigned long key[], hash_count_t keys, link_t *item)
     120static 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
     132static 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
     145static bool pos_match(unsigned long key[], size_t keys, const link_t *item)
    151146{
    152147        service_id_t service_id = (service_id_t)key[UPH_SID_KEY];
    … …  
    170165}
    171166
    172 static void pos_remove_callback(link_t *item)
    173 {
    174         /* nothing to do */
    175 }
    176 
    177 static hash_table_operations_t uph_ops = {
     167static hash_table_ops_t uph_ops = {
    178168        .hash = pos_hash,
    179         .compare = pos_compare,
    180         .remove_callback = pos_remove_callback,
     169        .key_hash = pos_key_hash,
     170        .match = pos_match,
     171        .equal = 0,
     172        .remove_callback = 0,
    181173};
    182174
    … …  
    187179static hash_table_t ui_hash;
    188180
    189 #define UIH_BUCKETS_LOG 12
    190 #define UIH_BUCKETS     (1 << UIH_BUCKETS_LOG)
    191 
    192181#define UIH_SID_KEY     0
    193182#define UIH_INDEX_KEY   1
    194183
    195 static hash_index_t idx_hash(unsigned long key[])
    196 {
    197         service_id_t service_id = (service_id_t)key[UIH_SID_KEY];
    198         fs_index_t index = (fs_index_t)key[UIH_INDEX_KEY];
    199 
    200         hash_index_t h;
    201 
    202         h = service_id & ((1 << (UIH_BUCKETS_LOG / 2)) - 1);
    203         h |= (index & ((1 << (UIH_BUCKETS_LOG / 2)) - 1)) <<
    204             (UIH_BUCKETS_LOG / 2);
    205 
    206         return h;
    207 }
    208 
    209 static int idx_compare(unsigned long key[], hash_count_t keys, link_t *item)
     184static 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
     196static 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
     208static bool idx_match(unsigned long key[], size_t keys, const link_t *item)
    210209{
    211210        service_id_t service_id = (service_id_t)key[UIH_SID_KEY];
    … …  
    234233}
    235234
    236 static hash_table_operations_t uih_ops = {
     235static hash_table_ops_t uih_ops = {
    237236        .hash = idx_hash,
    238         .compare = idx_compare,
     237        .key_hash = idx_key_hash,
     238        .match = idx_match,
     239        .equal = 0,
    239240        .remove_callback = idx_remove_callback,
    240241};
    … …  
    401402        }
    402403               
    403         unsigned long ikey[] = {
    404                 [UIH_SID_KEY] = service_id,
    405                 [UIH_INDEX_KEY] = fidx->index,
    406         };
    407        
    408         hash_table_insert(&ui_hash, ikey, &fidx->uih_link);
     404        hash_table_insert(&ui_hash, &fidx->uih_link);
    409405        fibril_mutex_lock(&fidx->lock);
    410406        fibril_mutex_unlock(&used_lock);
    … …  
    438434                }
    439435               
    440                 unsigned long ikey[] = {
    441                         [UIH_SID_KEY] = service_id,
    442                         [UIH_INDEX_KEY] = fidx->index,
    443                 };
    444        
    445436                fidx->pfc = pfc;
    446437                fidx->pdi = pdi;
    447438
    448                 hash_table_insert(&up_hash, pkey, &fidx->uph_link);
    449                 hash_table_insert(&ui_hash, ikey, &fidx->uih_link);
     439                hash_table_insert(&up_hash, &fidx->uph_link);
     440                hash_table_insert(&ui_hash, &fidx->uih_link);
    450441        }
    451442        fibril_mutex_lock(&fidx->lock);
    … …  
    457448void fat_idx_hashin(fat_idx_t *idx)
    458449{
    459         unsigned long pkey[] = {
    460                 [UPH_SID_KEY] = idx->service_id,
    461                 [UPH_PFC_KEY] = idx->pfc,
    462                 [UPH_PDI_KEY] = idx->pdi,
    463         };
    464 
    465         fibril_mutex_lock(&used_lock);
    466         hash_table_insert(&up_hash, pkey, &idx->uph_link);
     450        fibril_mutex_lock(&used_lock);
     451        hash_table_insert(&up_hash, &idx->uph_link);
    467452        fibril_mutex_unlock(&used_lock);
    468453}
    … …  
    470455void fat_idx_hashout(fat_idx_t *idx)
    471456{
    472         unsigned long pkey[] = {
    473                 [UPH_SID_KEY] = idx->service_id,
    474                 [UPH_PFC_KEY] = idx->pfc,
    475                 [UPH_PDI_KEY] = idx->pdi,
    476         };
    477 
    478         fibril_mutex_lock(&used_lock);
    479         hash_table_remove(&up_hash, pkey, 3);
     457        fibril_mutex_lock(&used_lock);
     458        hash_table_remove_item(&up_hash, &idx->uph_link);
    480459        fibril_mutex_unlock(&used_lock);
    481460}
    … …  
    532511int fat_idx_init(void)
    533512{
    534         if (!hash_table_create(&up_hash, UPH_BUCKETS, 3, &uph_ops))
     513        if (!hash_table_create(&up_hash, 0, 3, &uph_ops))
    535514                return ENOMEM;
    536         if (!hash_table_create(&ui_hash, UIH_BUCKETS, 2, &uih_ops)) {
     515        if (!hash_table_create(&ui_hash, 0, 2, &uih_ops)) {
    537516                hash_table_destroy(&up_hash);
    538517                return ENOMEM;

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

    r1c1da4b r0ca7286  
    7373#define SERVICES_KEYS        1
    7474#define SERVICES_KEY_HANDLE  0
    75 #define SERVICES_BUCKETS     256
    7675
    7776/* Implementation of hash table interface for the nodes hash table. */
    78 static hash_index_t services_hash(unsigned long key[])
    79 {
    80         return key[SERVICES_KEY_HANDLE] % SERVICES_BUCKETS;
    81 }
    82 
    83 static int services_compare(unsigned long key[], hash_count_t keys, link_t *item)
    84 {
     77
     78static size_t services_key_hash(unsigned long key[])
     79{
     80        return key[SERVICES_KEY_HANDLE];
     81}
     82
     83static 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
     93static bool services_match(unsigned long key[], size_t keys, const link_t *item)
     94{
     95        assert(keys == 1);
    8596        service_t *dev = hash_table_get_instance(item, service_t, link);
    8697        return (dev->service_id == (service_id_t) key[SERVICES_KEY_HANDLE]);
    … …  
    92103}
    93104
    94 static hash_table_operations_t services_ops = {
     105static hash_table_ops_t services_ops = {
    95106        .hash = services_hash,
    96         .compare = services_compare,
     107        .key_hash = services_key_hash,
     108        .match = services_match,
     109        .equal = 0,
    97110        .remove_callback = services_remove_callback
    98111};
    … …  
    256269                         * below.
    257270                         */
    258                         hash_table_insert(&services, key, &dev->link);
     271                        hash_table_insert(&services, &dev->link);
    259272                       
    260273                        /*
    … …  
    450463bool locfs_init(void)
    451464{
    452         if (!hash_table_create(&services, SERVICES_BUCKETS,
    453             SERVICES_KEYS, &services_ops))
     465        if (!hash_table_create(&services, 0,  SERVICES_KEYS, &services_ops))
    454466                return false;
    455467       

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

    r1c1da4b r0ca7286  
    4040#define OPEN_NODES_SERVICE_KEY 0
    4141#define OPEN_NODES_INODE_KEY 1
    42 #define OPEN_NODES_BUCKETS 256
    4342
    4443static bool check_magic_number(uint16_t magic, bool *native,
    … …  
    6160static int mfs_unlink(fs_node_t *, fs_node_t *, const char *name);
    6261static int mfs_destroy_node(fs_node_t *fn);
    63 static hash_index_t open_nodes_hash(unsigned long key[]);
    64 static int open_nodes_compare(unsigned long key[], hash_count_t keys,
    65     link_t *item);
    66 static void open_nodes_remove_cb(link_t *link);
     62static size_t open_nodes_hash(const link_t *item);
     63static size_t open_nodes_key_hash(unsigned long key[]);
     64static bool open_nodes_match(unsigned long key[], size_t keys,
     65    const link_t *item);
    6766static int mfs_node_get(fs_node_t **rfn, service_id_t service_id,
    6867    fs_index_t index);
    … …  
    9594
    9695/* Hash table interface for open nodes hash table */
    97 static hash_index_t
    98 open_nodes_hash(unsigned long key[])
    99 {
    100         /* TODO: This is very simple and probably can be improved */
    101         return key[OPEN_NODES_INODE_KEY] % OPEN_NODES_BUCKETS;
    102 }
    103 
    104 static int
    105 open_nodes_compare(unsigned long key[], hash_count_t keys,
    106     link_t *item)
    107 {
     96
     97static size_t
     98open_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;
     105}
     106
     107static size_t
     108open_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);
     118}
     119
     120static bool
     121open_nodes_match(unsigned long key[], size_t keys, const link_t *item)
     122{
     123        assert(keys == 2);
    108124        struct mfs_node *mnode = hash_table_get_instance(item, struct mfs_node, link);
    109         assert(keys > 0);
    110         if (mnode->instance->service_id !=
    111             ((service_id_t) key[OPEN_NODES_SERVICE_KEY])) {
    112                 return false;
    113         }
    114         if (keys == 1) {
    115                 return true;
    116         }
    117         assert(keys == 2);
    118         return (mnode->ino_i->index == key[OPEN_NODES_INODE_KEY]);
    119 }
    120 
    121 static void
    122 open_nodes_remove_cb(link_t *link)
    123 {
    124         /* We don't use remove callback for this hash table */
    125 }
    126 
    127 static hash_table_operations_t open_nodes_ops = {
     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
     132
     133static hash_table_ops_t open_nodes_ops = {
    128134        .hash = open_nodes_hash,
    129         .compare = open_nodes_compare,
    130         .remove_callback = open_nodes_remove_cb,
     135        .key_hash = open_nodes_key_hash,
     136        .match = open_nodes_match,
     137        .equal = 0,
     138        .remove_callback = 0,
    131139};
    132140
    … …  
    134142mfs_global_init(void)
    135143{
    136         if (!hash_table_create(&open_nodes, OPEN_NODES_BUCKETS,
    137             OPEN_NODES_KEYS, &open_nodes_ops)) {
     144        if (!hash_table_create(&open_nodes, 0, OPEN_NODES_KEYS, &open_nodes_ops)) {
    138145                return ENOMEM;
    139146        }
    … …  
    408415        link_initialize(&mnode->link);
    409416
    410         unsigned long key[] = {
    411                 [OPEN_NODES_SERVICE_KEY] = inst->service_id,
    412                 [OPEN_NODES_INODE_KEY] = inum,
    413         };
    414 
    415417        fibril_mutex_lock(&open_nodes_lock);
    416         hash_table_insert(&open_nodes, key, &mnode->link);
     418        hash_table_insert(&open_nodes, &mnode->link);
    417419        fibril_mutex_unlock(&open_nodes_lock);
    418420        inst->open_nodes_cnt++;
    … …  
    621623        *rfn = node;
    622624
    623         hash_table_insert(&open_nodes, key, &mnode->link);
     625        hash_table_insert(&open_nodes, &mnode->link);
    624626        inst->open_nodes_cnt++;
    625627

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

    r1c1da4b r0ca7286  
    5656#define max(a, b)               ((a) > (b) ? (a) : (b))
    5757
    58 #define NODES_BUCKETS   256
    59 
    6058/** All root nodes have index 0. */
    6159#define TMPFS_SOME_ROOT         0
    … …  
    146144
    147145/* Implementation of hash table interface for the nodes hash table. */
    148 static hash_index_t nodes_hash(unsigned long key[])
    149 {
    150         return key[NODES_KEY_INDEX] % NODES_BUCKETS;
    151 }
    152 
    153 static int nodes_compare(unsigned long key[], hash_count_t keys, link_t *item)
     146static 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
     155static 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
     167static bool nodes_match(unsigned long key[], size_t keys, const link_t *item)
    154168{
    155169        tmpfs_node_t *nodep = hash_table_get_instance(item, tmpfs_node_t,
    … …  
    192206
    193207/** TMPFS nodes hash table operations. */
    194 hash_table_operations_t nodes_ops = {
     208hash_table_ops_t nodes_ops = {
    195209        .hash = nodes_hash,
    196         .compare = nodes_compare,
     210        .key_hash = nodes_key_hash,
     211        .match = nodes_match,
     212        .equal = 0,
    197213        .remove_callback = nodes_remove_callback
    198214};
    … …  
    220236bool tmpfs_init(void)
    221237{
    222         if (!hash_table_create(&nodes, NODES_BUCKETS, 2, &nodes_ops))
     238        if (!hash_table_create(&nodes, 0, 2, &nodes_ops))
    223239                return false;
    224240       
    … …  
    331347
    332348        /* Insert the new node into the nodes hash table. */
    333         unsigned long key[] = {
    334                 [NODES_KEY_DEV] = nodep->service_id,
    335                 [NODES_KEY_INDEX] = nodep->index
    336         };
    337         hash_table_insert(&nodes, key, &nodep->nh_link);
     349        hash_table_insert(&nodes, &nodep->nh_link);
    338350        *rfn = FS_NODE(nodep);
    339351        return EOK;

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

    r1c1da4b r0ca7286  
    5454#include <stdio.h>
    5555
    56 #define TRANS_TABLE_CHAINS 256
    57 
    5856/*
    5957 * Hash table operations for the transition function.
    6058 */
    6159
    62 static hash_index_t trans_op_hash(unsigned long key[]);
    63 static int trans_op_compare(unsigned long key[], hash_count_t keys,
    64     link_t *item);
    65 static void trans_op_remove_callback(link_t *item);
    66 
    67 static hash_table_operations_t trans_ops = {
     60static size_t trans_op_hash(const link_t *item);
     61static size_t trans_op_key_hash(unsigned long key[]);
     62static bool trans_op_match(unsigned long key[], size_t keys, const link_t *item);
     63
     64static hash_table_ops_t trans_ops = {
    6865        .hash = trans_op_hash,
    69         .compare = trans_op_compare,
    70         .remove_callback = trans_op_remove_callback
     66        .key_hash = trans_op_key_hash,
     67        .match = trans_op_match,
     68        .equal = 0,
     69        .remove_callback = 0
    7170};
    7271
    … …  
    7574static gsp_trans_t *trans_new(void);
    7675
    77 /** Initialise scancode parser. */
     76/** Initialize scancode parser. */
    7877void gsp_init(gsp_t *p)
    7978{
    8079        p->states = 1;
    81         hash_table_create(&p->trans, TRANS_TABLE_CHAINS, 2, &trans_ops);
     80        hash_table_create(&p->trans, 0, 2, &trans_ops);
    8281}
    8382
    … …  
    242241static void trans_insert(gsp_t *p, gsp_trans_t *t)
    243242{
    244         unsigned long key[2];
    245 
    246         key[0] = t->old_state;
    247         key[1] = t->input;
    248 
    249         hash_table_insert(&p->trans, key, &t->link);
     243        hash_table_insert(&p->trans, &t->link);
    250244}
    251245
    … …  
    268262 */
    269263
    270 static hash_index_t trans_op_hash(unsigned long key[])
    271 {
    272         return (key[0] * 17 + key[1]) % TRANS_TABLE_CHAINS;
    273 }
    274 
    275 static int trans_op_compare(unsigned long key[], hash_count_t keys,
    276     link_t *item)
    277 {
    278         gsp_trans_t *t;
    279 
    280         t = hash_table_get_instance(item, gsp_trans_t, link);
     264static size_t trans_op_key_hash(unsigned long key[])
     265{
     266        return (key[0] * 17 + key[1]);
     267}
     268
     269static 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
     280static 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);
    281283        return ((key[0] == (unsigned long) t->old_state)
    282284            && (key[1] == (unsigned long) t->input));
    283 }
    284 
    285 static void trans_op_remove_callback(link_t *item)
    286 {
    287285}
    288286

  • uspace/srv/ns/service.c

    r1c1da4b r0ca7286  
    4040#include "ns.h"
    4141
    42 #define SERVICE_HASH_TABLE_CHAINS  20
    4342
    4443/** Service hash table item. */
    … …  
    5857 *
    5958 */
    60 static hash_index_t service_hash(unsigned long key[])
     59static size_t service_key_hash(unsigned long key[])
    6160{
    6261        assert(key);
    63         return (key[0] % SERVICE_HASH_TABLE_CHAINS);
     62        return key[0];
     63}
     64
     65static size_t service_hash(const link_t *item)
     66{
     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);
    6470}
    6571
    … …  
    7985 *
    8086 */
    81 static int service_compare(unsigned long key[], hash_count_t keys, link_t *item)
     87static bool service_match(unsigned long key[], size_t keys, const link_t *item)
    8288{
    8389        assert(key);
    … …  
    105111
    106112/** Operations for service hash table. */
    107 static hash_table_operations_t service_hash_table_ops = {
     113static hash_table_ops_t service_hash_table_ops = {
    108114        .hash = service_hash,
    109         .compare = service_compare,
     115        .key_hash = service_key_hash,
     116        .match = service_match,
     117        .equal = 0,
    110118        .remove_callback = service_remove
    111119};
    … …  
    127135int service_init(void)
    128136{
    129         if (!hash_table_create(&service_hash_table, SERVICE_HASH_TABLE_CHAINS,
    130             3, &service_hash_table_ops)) {
     137        if (!hash_table_create(&service_hash_table, 0, 3, &service_hash_table_ops)) {
    131138                printf(NAME ": No memory available for services\n");
    132139                return ENOMEM;
    … …  
    193200        hs->phone = phone;
    194201        hs->in_phone_hash = call->in_phone_hash;
    195         hash_table_insert(&service_hash_table, keys, &hs->link);
     202        hash_table_insert(&service_hash_table, &hs->link);
    196203       
    197204        return EOK;

  • uspace/srv/ns/task.c

    r1c1da4b r0ca7286  
    4343#include "ns.h"
    4444
    45 #define TASK_HASH_TABLE_CHAINS  256
    46 #define P2I_HASH_TABLE_CHAINS   256
    4745
    4846/* TODO:
    … …  
    7169 *
    7270 */
    73 static hash_index_t task_hash(unsigned long key[])
    74 {
    75         assert(key);
    76         return (LOWER32(key[0]) % TASK_HASH_TABLE_CHAINS);
     71static 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
     79static 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);
    7789}
    7890
    … …  
    8698 *
    8799 */
    88 static int task_compare(unsigned long key[], hash_count_t keys, link_t *item)
     100static bool task_match(unsigned long key[], size_t keys, const link_t *item)
    89101{
    90102        assert(key);
    91         assert(keys <= 2);
     103        assert(keys == 2);
    92104        assert(item);
    93105       
    94106        hashed_task_t *ht = hash_table_get_instance(item, hashed_task_t, link);
    95107       
    96         if (keys == 2)
    97                 return ((LOWER32(key[1]) == UPPER32(ht->id))
    98                     && (LOWER32(key[0]) == LOWER32(ht->id)));
    99         else
    100                 return (LOWER32(key[0]) == LOWER32(ht->id));
     108        return (key[0] == LOWER32(ht->id))
     109                && (key[1] == UPPER32(ht->id));
    101110}
    102111
    … …  
    113122
    114123/** Operations for task hash table. */
    115 static hash_table_operations_t task_hash_table_ops = {
     124static hash_table_ops_t task_hash_table_ops = {
    116125        .hash = task_hash,
    117         .compare = task_compare,
     126        .key_hash = task_key_hash,
     127        .match = task_match,
     128        .equal = 0,
    118129        .remove_callback = task_remove
    119130};
    … …  
    135146 *
    136147 */
    137 static hash_index_t p2i_hash(unsigned long key[])
     148static size_t p2i_key_hash(unsigned long key[])
    138149{
    139150        assert(key);
    140         return (key[0] % TASK_HASH_TABLE_CHAINS);
     151        return key[0];
     152}
     153
     154static 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);
    141159}
    142160
    … …  
    150168 *
    151169 */
    152 static int p2i_compare(unsigned long key[], hash_count_t keys, link_t *item)
     170static bool p2i_match(unsigned long key[], size_t keys, const link_t *item)
    153171{
    154172        assert(key);
    … …  
    173191
    174192/** Operations for task hash table. */
    175 static hash_table_operations_t p2i_ops = {
     193static hash_table_ops_t p2i_ops = {
    176194        .hash = p2i_hash,
    177         .compare = p2i_compare,
     195        .key_hash = p2i_key_hash,
     196        .match = p2i_match,
     197        .equal = 0,
    178198        .remove_callback = p2i_remove
    179199};
    … …  
    193213int task_init(void)
    194214{
    195         if (!hash_table_create(&task_hash_table, TASK_HASH_TABLE_CHAINS,
    196             2, &task_hash_table_ops)) {
     215        if (!hash_table_create(&task_hash_table, 0, 2, &task_hash_table_ops)) {
    197216                printf(NAME ": No memory available for tasks\n");
    198217                return ENOMEM;
    199218        }
    200219       
    201         if (!hash_table_create(&phone_to_id, P2I_HASH_TABLE_CHAINS,
    202             1, &p2i_ops)) {
     220        if (!hash_table_create(&phone_to_id, 0, 1, &p2i_ops)) {
    203221                printf(NAME ": No memory available for tasks\n");
    204222                return ENOMEM;
    … …  
    293311int ns_task_id_intro(ipc_call_t *call)
    294312{
    295         unsigned long keys[2];
    296313       
    297314        task_id_t id = MERGE_LOUP32(IPC_GET_ARG1(*call), IPC_GET_ARG2(*call));
    298         keys[0] = call->in_phone_hash;
     315
     316        unsigned long keys[] = { call->in_phone_hash };
    299317       
    300318        link_t *link = hash_table_find(&phone_to_id, keys);
    … …  
    317335        entry->in_phone_hash = call->in_phone_hash;
    318336        entry->id = id;
    319         hash_table_insert(&phone_to_id, keys, &entry->link);
     337        hash_table_insert(&phone_to_id, &entry->link);
    320338       
    321339        /*
    322340         * Insert into the main table.
    323341         */
    324        
    325         keys[0] = LOWER32(id);
    326         keys[1] = UPPER32(id);
    327342       
    328343        link_initialize(&ht->link);
    … …  
    331346        ht->have_rval = false;
    332347        ht->retval = -1;
    333         hash_table_insert(&task_hash_table, keys, &ht->link);
     348        hash_table_insert(&task_hash_table, &ht->link);
    334349       
    335350        return EOK;

  • uspace/srv/vfs/vfs_node.c

    r1c1da4b r0ca7286  
    5858#define KEY_INDEX       2
    5959
    60 static hash_index_t nodes_hash(unsigned long []);
    61 static int nodes_compare(unsigned long [], hash_count_t, link_t *);
    62 static void nodes_remove_callback(link_t *);
     60static size_t nodes_key_hash(unsigned long []);
     61static size_t nodes_hash(const link_t *);
     62static bool nodes_match(unsigned long [], size_t, const link_t *);
    6363
    6464/** VFS node hash table operations. */
    65 hash_table_operations_t nodes_ops = {
     65hash_table_ops_t nodes_ops = {
    6666        .hash = nodes_hash,
    67         .compare = nodes_compare,
    68         .remove_callback = nodes_remove_callback
     67        .key_hash = nodes_key_hash,
     68        .match = nodes_match,
     69        .equal = 0,
     70        .remove_callback = 0,
    6971};
    7072
    … …  
    7577bool vfs_nodes_init(void)
    7678{
    77         return hash_table_create(&nodes, NODES_BUCKETS, 3, &nodes_ops);
     79        return hash_table_create(&nodes, 0, 3, &nodes_ops);
    7880}
    7981
    … …  
    207209                link_initialize(&node->nh_link);
    208210                fibril_rwlock_initialize(&node->contents_rwlock);
    209                 hash_table_insert(&nodes, key, &node->nh_link);
     211                hash_table_insert(&nodes, &node->nh_link);
    210212        } else {
    211213                node = hash_table_get_instance(tmp, vfs_node_t, nh_link);
    … …  
    240242}
    241243
    242 hash_index_t nodes_hash(unsigned long key[])
    243 {
    244         hash_index_t a = key[KEY_FS_HANDLE] << (NODES_BUCKETS_LOG / 4);
    245         hash_index_t b = (a | key[KEY_DEV_HANDLE]) << (NODES_BUCKETS_LOG / 2);
    246        
    247         return (b | key[KEY_INDEX]) & (NODES_BUCKETS - 1);
    248 }
    249 
    250 int nodes_compare(unsigned long key[], hash_count_t keys, link_t *item)
     244size_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
     254size_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
     268bool nodes_match(unsigned long key[], size_t keys, const link_t *item)
    251269{
    252270        vfs_node_t *node = hash_table_get_instance(item, vfs_node_t, nh_link);
    … …  
    256274}
    257275
    258 void nodes_remove_callback(link_t *item)
    259 {
    260 }
    261276
    262277struct refcnt_data {
    … …  
    267282};
    268283
    269 static void refcnt_visitor(link_t *item, void *arg)
     284static bool refcnt_visitor(link_t *item, void *arg)
    270285{
    271286        vfs_node_t *node = hash_table_get_instance(item, vfs_node_t, nh_link);
    … …  
    275290            (node->service_id == rd->service_id))
    276291                rd->refcnt += node->refcnt;
     292       
     293        return true;
    277294}
    278295
Note: See TracChangeset for help on using the changeset viewer.