Changeset bc216a0 in mainline for uspace/lib/c


Ignore:
Timestamp:
2012-08-07T22:13:44Z (13 years ago)
Author:
Adam Hraska <adam.hraska+hos@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
da68871a
Parents:
b17518e
Message:

Refactored any users of hash_table to use opaque void* keys instead of the cumbersome unsigned long[] keys. Switched from the ad hoc computations of hashes of multiple values to hash_combine().

Location:
uspace/lib/c
Files:
1 added
4 edited

Legend:

Unmodified
Added
Removed

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

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

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

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

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

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

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

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