Changeset 9f4067b6 in mainline for uspace/lib


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

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

Location:
uspace/lib
Files:
1 added
2 deleted
13 edited

Legend:

Unmodified
Added
Removed

  • uspace/lib/block/block.c

    rd1ef4a1 r9f4067b6  
    6262static LIST_INITIALIZE(dcl);
    6363
    64 #define CACHE_BUCKETS_LOG2  10
    65 #define CACHE_BUCKETS       (1 << CACHE_BUCKETS_LOG2)
    6664
    6765typedef struct {
    … …  
    233231}
    234232
    235 static hash_index_t cache_hash(unsigned long *key)
    236 {
    237         return MERGE_LOUP32(key[0], key[1]) & (CACHE_BUCKETS - 1);
    238 }
    239 
    240 static int cache_compare(unsigned long *key, hash_count_t keys, link_t *item)
    241 {
    242         block_t *b = hash_table_get_instance(item, block_t, hash_link);
    243         return b->lba == MERGE_LOUP32(key[0], key[1]);
    244 }
    245 
    246 static void cache_remove_callback(link_t *item)
    247 {
    248 }
    249 
    250 static hash_table_operations_t cache_ops = {
     233static size_t cache_key_hash(void *key)
     234{
     235        aoff64_t *lba = (aoff64_t*)key;
     236        return *lba;
     237}
     238
     239static size_t cache_hash(const ht_link_t *item)
     240{
     241        block_t *b = hash_table_get_inst(item, block_t, hash_link);
     242        return b->lba;
     243}
     244
     245static bool cache_key_equal(void *key, const ht_link_t *item)
     246{
     247        aoff64_t *lba = (aoff64_t*)key;
     248        block_t *b = hash_table_get_inst(item, block_t, hash_link);
     249        return b->lba == *lba;
     250}
     251
     252
     253static hash_table_ops_t cache_ops = {
    251254        .hash = cache_hash,
    252         .compare = cache_compare,
    253         .remove_callback = cache_remove_callback
     255        .key_hash = cache_key_hash,
     256        .key_equal = cache_key_equal,
     257        .equal = NULL,
     258        .remove_callback = NULL
    254259};
    255260
    … …  
    282287        cache->blocks_cluster = cache->lblock_size / devcon->pblock_size;
    283288
    284         if (!hash_table_create(&cache->block_hash, CACHE_BUCKETS, 2,
    285             &cache_ops)) {
     289        if (!hash_table_create(&cache->block_hash, 0, 0, &cache_ops)) {
    286290                free(cache);
    287291                return ENOMEM;
    … …  
    321325                }
    322326
    323                 unsigned long key[2] = {
    324                         LOWER32(b->lba),
    325                         UPPER32(b->lba)
    326                 };
    327                 hash_table_remove(&cache->block_hash, key, 2);
     327                hash_table_remove_item(&cache->block_hash, &b->hash_link);
    328328               
    329329                free(b->data);
    … …  
    357357        fibril_rwlock_initialize(&b->contents_lock);
    358358        link_initialize(&b->free_link);
    359         link_initialize(&b->hash_link);
    360359}
    361360
    … …  
    377376        cache_t *cache;
    378377        block_t *b;
    379         link_t *l;
    380         unsigned long key[2] = {
    381                 LOWER32(ba),
    382                 UPPER32(ba)
    383         };
     378        link_t *link;
    384379
    385380        int rc;
    … …  
    397392
    398393        fibril_mutex_lock(&cache->lock);
    399         l = hash_table_find(&cache->block_hash, key);
    400         if (l) {
     394        ht_link_t *hlink = hash_table_find(&cache->block_hash, &ba);
     395        if (hlink) {
    401396found:
    402397                /*
    403398                 * We found the block in the cache.
    404399                 */
    405                 b = hash_table_get_instance(l, block_t, hash_link);
     400                b = hash_table_get_inst(hlink, block_t, hash_link);
    406401                fibril_mutex_lock(&b->lock);
    407402                if (b->refcnt++ == 0)
    … …  
    441436                                goto out;
    442437                        }
    443                         l = list_first(&cache->free_list);
    444                         b = list_get_instance(l, block_t, free_link);
     438                        link = list_first(&cache->free_list);
     439                        b = list_get_instance(link, block_t, free_link);
    445440
    446441                        fibril_mutex_lock(&b->lock);
    … …  
    479474                                        goto retry;
    480475                                }
    481                                 l = hash_table_find(&cache->block_hash, key);
    482                                 if (l) {
     476                                hlink = hash_table_find(&cache->block_hash, &ba);
     477                                if (hlink) {
    483478                                        /*
    484479                                         * Someone else must have already
    … …  
    502497                         */
    503498                        list_remove(&b->free_link);
    504                         unsigned long temp_key[2] = {
    505                                 LOWER32(b->lba),
    506                                 UPPER32(b->lba)
    507                         };
    508                         hash_table_remove(&cache->block_hash, temp_key, 2);
     499                        hash_table_remove_item(&cache->block_hash, &b->hash_link);
    509500                }
    510501
    … …  
    514505                b->lba = ba;
    515506                b->pba = ba_ltop(devcon, b->lba);
    516                 hash_table_insert(&cache->block_hash, key, &b->hash_link);
     507                hash_table_insert(&cache->block_hash, &b->hash_link);
    517508
    518509                /*
    … …  
    622613                         * Take the block out of the cache and free it.
    623614                         */
    624                         unsigned long key[2] = {
    625                                 LOWER32(block->lba),
    626                                 UPPER32(block->lba)
    627                         };
    628                         hash_table_remove(&cache->block_hash, key, 2);
     615                        hash_table_remove_item(&cache->block_hash, &block->hash_link);
    629616                        fibril_mutex_unlock(&block->lock);
    630617                        free(block->data);

  • uspace/lib/block/block.h

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

  • uspace/lib/c/Makefile

    rd1ef4a1 r9f4067b6  
    124124        generic/adt/list.c \
    125125        generic/adt/hash_table.c \
    126         generic/adt/hash_set.c \
    127126        generic/adt/dynamic_fifo.c \
    128127        generic/adt/char_map.c \

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

    rd1ef4a1 r9f4067b6  
    11/*
    22 * Copyright (c) 2008 Jakub Jermar
     3 * Copyright (c) 2012 Adam Hraska
     4 *
    35 * All rights reserved.
    46 *
    … …  
    3436
    3537/*
    36  * This is an implementation of generic chained hash table.
     38 * This is an implementation of a generic resizable chained hash table.
     39 *
     40 * The table grows to 2*n+1 buckets each time, starting at n == 89,
     41 * per Thomas Wang's recommendation:
     42 * http://www.concentric.net/~Ttwang/tech/hashsize.htm
     43 *
     44 * This policy produces prime table sizes for the first five resizes
     45 * and generally produces table sizes which are either prime or
     46 * have fairly large (prime/odd) divisors. Having a prime table size
     47 * mitigates the use of suboptimal hash functions and distributes
     48 * items over the whole table.
    3749 */
    3850
    … …  
    4456#include <str.h>
    4557
     58/* Optimal initial bucket count. See comment above. */
     59#define HT_MIN_BUCKETS  89
     60/* The table is resized when the average load per bucket exceeds this number. */
     61#define HT_MAX_LOAD     2
     62
     63
     64static size_t round_up_size(size_t);
     65static bool alloc_table(size_t, list_t **);
     66static void clear_items(hash_table_t *);
     67static void resize(hash_table_t *, size_t);
     68static void grow_if_needed(hash_table_t *);
     69static void shrink_if_needed(hash_table_t *);
     70
     71/* Dummy do nothing callback to invoke in place of remove_callback == NULL. */
     72static void nop_remove_callback(ht_link_t *item)
     73{
     74        /* no-op */
     75}
     76
     77
    4678/** Create chained hash table.
    4779 *
    4880 * @param h        Hash table structure. Will be initialized by this call.
    49  * @param m        Number of hash table buckets.
     81 * @param init_size Initial desired number of hash table buckets. Pass zero
     82 *                 if you want the default initial size.
    5083 * @param max_keys Maximal number of keys needed to identify an item.
    51  * @param op       Hash table operations structure.
     84 * @param op       Hash table operations structure. remove_callback()
     85 *                 is optional and can be NULL if no action is to be taken
     86 *                 upon removal. equal() is optional if and only if
     87 *                 hash_table_insert_unique() will never be invoked.
     88 *                 All other operations are mandatory.
    5289 *
    5390 * @return True on success
    5491 *
    5592 */
    56 bool hash_table_create(hash_table_t *h, hash_count_t m, hash_count_t max_keys,
    57     hash_table_operations_t *op)
     93bool hash_table_create(hash_table_t *h, size_t init_size, size_t max_load,
     94    hash_table_ops_t *op)
    5895{
    5996        assert(h);
    60         assert(op && op->hash && op->compare);
    61         assert(max_keys > 0);
    62        
    63         h->entry = malloc(m * sizeof(list_t));
    64         if (!h->entry)
     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)
    65101                return false;
    66102       
    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;
    74         h->max_keys = max_keys;
     103        h->bucket_cnt = round_up_size(init_size);
     104       
     105        if (!alloc_table(h->bucket_cnt, &h->bucket))
     106                return false;
     107       
     108        h->max_load = (max_load == 0) ? HT_MAX_LOAD : max_load;
     109        h->item_cnt = 0;
    75110        h->op = op;
     111        h->full_item_cnt = h->max_load * h->bucket_cnt;
     112        h->apply_ongoing = false;
     113
     114        if (h->op->remove_callback == NULL) {
     115                h->op->remove_callback = nop_remove_callback;
     116        }
    76117       
    77118        return true;
    78119}
    79120
     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
    80153/** Remove all elements from the hash table
    81154 *
    … …  
    84157void hash_table_clear(hash_table_t *h)
    85158{
    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;
     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       
     176        for (size_t idx = 0; idx < h->bucket_cnt; ++idx) {
     177                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                       
    94181                        list_remove(cur);
    95                         h->op->remove_callback(cur);
    96                 }
    97         }
    98 }
    99 
    100 /** Destroy a hash table instance.
    101  *
    102  * @param h Hash table to be destroyed.
    103  *
    104  */
    105 void hash_table_destroy(hash_table_t *h)
    106 {
    107         assert(h);
    108         assert(h->entry);
    109        
    110         free(h->entry);
     182                        h->op->remove_callback(cur_link);
     183                }
     184        }
     185       
     186        h->item_cnt = 0;
    111187}
    112188
    … …  
    117193 * @param item Item to be inserted into the hash table.
    118194 */
    119 void hash_table_insert(hash_table_t *h, unsigned long key[], link_t *item)
     195void hash_table_insert(hash_table_t *h, ht_link_t *item)
    120196{
    121197        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]);
     198        assert(h && h->bucket);
     199        assert(!h->apply_ongoing);
     200       
     201        size_t idx = h->op->hash(item) % h->bucket_cnt;
     202       
     203        list_append(&item->link, &h->bucket[idx]);
     204        ++h->item_cnt;
     205        grow_if_needed(h);
     206}
     207
     208
     209/** Insert item into a hash table if not already present.
     210 *
     211 * @param h    Hash table.
     212 * @param key  Array of all keys necessary to compute hash index.
     213 * @param item Item to be inserted into the hash table.
     214 *
     215 * @return False if such an item had already been inserted.
     216 * @return True if the inserted item was the only item with such a lookup key.
     217 */
     218bool hash_table_insert_unique(hash_table_t *h, ht_link_t *item)
     219{
     220        assert(item);
     221        assert(h && h->bucket && h->bucket_cnt);
     222        assert(h->op && h->op->hash && h->op->equal);
     223        assert(!h->apply_ongoing);
     224       
     225        size_t idx = h->op->hash(item) % h->bucket_cnt;
     226       
     227        /* Check for duplicates. */
     228        list_foreach(h->bucket[idx], cur) {
     229                /*
     230                 * We could filter out items using their hashes first, but
     231                 * calling equal() might very well be just as fast.
     232                 */
     233                ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link);
     234                if (h->op->equal(cur_link, item))
     235                        return false;
     236        }
     237       
     238        list_append(&item->link, &h->bucket[idx]);
     239        ++h->item_cnt;
     240        grow_if_needed(h);
     241       
     242        return true;
    128243}
    129244
    … …  
    136251 *
    137252 */
    138 link_t *hash_table_find(hash_table_t *h, unsigned long key[])
    139 {
    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.
    149                          */
    150                         return cur;
    151                 }
    152         }
    153        
     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
     259        list_foreach(h->bucket[idx], cur) {
     260                ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link);
     261                /*
     262                 * Is this is the item we are looking for? We could have first
     263                 * checked if the hashes match but op->key_equal() may very well be
     264                 * just as fast as op->hash().
     265                 */
     266                if (h->op->key_equal(key, cur_link)) {
     267                        return cur_link;
     268                }
     269        }
     270       
     271        return NULL;
     272}
     273
     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
    154294        return NULL;
    155295}
    … …  
    163303 *             the hash table.
    164304 * @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 &&
    170             h->op->remove_callback);
    171         assert(keys <= h->max_keys);
    172        
    173         if (keys == h->max_keys) {
    174                 /*
    175                  * All keys are known, hash_table_find() can be used to find the
    176                  * entry.
     305 *
     306 * @return Returns the number of removed items.
     307 */
     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;
     331}
     332
     333/** Removes an item already present in the table. The item must be in the table.*/
     334void hash_table_remove_item(hash_table_t *h, ht_link_t *item)
     335{
     336        assert(item);
     337        assert(h && h->bucket);
     338        assert(link_in_use(&item->link));
     339
     340        list_remove(&item->link);
     341        --h->item_cnt;
     342        h->op->remove_callback(item);
     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       
     365        for (size_t idx = 0; idx < h->bucket_cnt; ++idx) {
     366                list_foreach_safe(h->bucket[idx], cur, next) {
     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);
     381}
     382
     383/** Rounds up size to the nearest suitable table size. */
     384static size_t round_up_size(size_t size)
     385{
     386        size_t rounded_size = HT_MIN_BUCKETS;
     387       
     388        while (rounded_size < size) {
     389                rounded_size = 2 * rounded_size + 1;
     390        }
     391       
     392        return rounded_size;
     393}
     394
     395/** Allocates and initializes the desired number of buckets. True if successful.*/
     396static bool alloc_table(size_t bucket_cnt, list_t **pbuckets)
     397{
     398        assert(pbuckets && HT_MIN_BUCKETS <= bucket_cnt);
     399               
     400        list_t *buckets = malloc(bucket_cnt * sizeof(list_t));
     401        if (!buckets)
     402                return false;
     403       
     404        for (size_t i = 0; i < bucket_cnt; i++)
     405                list_initialize(&buckets[i]);
     406
     407        *pbuckets = buckets;
     408        return true;
     409}
     410
     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) {
     416                /*
     417                 * Keep the bucket_cnt odd (possibly also prime).
     418                 * Shrink from 2n + 1 to n. Integer division discards the +1.
    177419                 */
    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                
     420                size_t new_bucket_cnt = h->bucket_cnt / 2;
     421                resize(h, new_bucket_cnt);
     422        }
     423}
     424
     425/** Grows the table if table load exceeds the maximum allowed. */
     426static inline void grow_if_needed(hash_table_t *h)
     427{
     428        /* Grow the table if the average bucket load exceeds the maximum. */
     429        if (h->full_item_cnt < h->item_cnt) {
     430                /* Keep the bucket_cnt odd (possibly also prime). */
     431                size_t new_bucket_cnt = 2 * h->bucket_cnt + 1;
     432                resize(h, new_bucket_cnt);
     433        }
     434}
     435
     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)
    185444                return;
    186         }
    187        
    188         /*
    189          * Fewer keys were passed.
    190          * Any partially matching entries are to be removed.
    191          */
    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;
     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]);
    207461                        }
    208462                }
    209463        }
    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 }
     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
    237471
    238472/** @}

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

    rd1ef4a1 r9f4067b6  
    116116#include "private/libc.h"
    117117
    118 #define CLIENT_HASH_TABLE_BUCKETS  32
    119 #define CONN_HASH_TABLE_BUCKETS    32
    120118
    121119/** Session data */
    … …  
    205203/* Client connection data */
    206204typedef struct {
    207         link_t link;
     205        ht_link_t link;
    208206       
    209207        task_id_t in_task_id;
    … …  
    217215       
    218216        /** Hash table link. */
    219         link_t link;
     217        ht_link_t link;
    220218       
    221219        /** Incoming client task ID. */
    … …  
    393391static LIST_INITIALIZE(timeout_list);
    394392
    395 static hash_index_t client_hash(unsigned long key[])
    396 {
    397         assert(key);
    398        
    399         return (((key[0]) >> 4) % CLIENT_HASH_TABLE_BUCKETS);
    400 }
    401 
    402 static int client_compare(unsigned long key[], hash_count_t keys, link_t *item)
    403 {
    404         assert(key);
    405         assert(keys == 2);
    406         assert(item);
    407        
    408         client_t *client = hash_table_get_instance(item, client_t, link);
    409         return (key[0] == LOWER32(client->in_task_id) &&
    410             (key[1] == UPPER32(client->in_task_id)));
    411 }
    412 
    413 static void client_remove(link_t *item)
    414 {
    415 }
     393static size_t client_key_hash(void *k)
     394{
     395        task_id_t key = *(task_id_t*)k;
     396        return key;
     397}
     398
     399static size_t client_hash(const ht_link_t *item)
     400{
     401        client_t *client = hash_table_get_inst(item, client_t, link);
     402        return client_key_hash(&client->in_task_id);
     403}
     404
     405static bool client_key_equal(void *k, const ht_link_t *item)
     406{
     407        task_id_t key = *(task_id_t*)k;
     408        client_t *client = hash_table_get_inst(item, client_t, link);
     409        return key == client->in_task_id;
     410}
     411
    416412
    417413/** Operations for the client hash table. */
    418 static hash_table_operations_t client_hash_table_ops = {
     414static hash_table_ops_t client_hash_table_ops = {
    419415        .hash = client_hash,
    420         .compare = client_compare,
    421         .remove_callback = client_remove
     416        .key_hash = client_key_hash,
     417        .key_equal = client_key_equal,
     418        .equal = NULL,
     419        .remove_callback = NULL
    422420};
    423421
    … …  
    429427 *
    430428 */
    431 static hash_index_t conn_hash(unsigned long key[])
    432 {
    433         assert(key);
    434        
    435         return (((key[0]) >> 4) % CONN_HASH_TABLE_BUCKETS);
    436 }
    437 
    438 /** Compare hash table item with a key.
    439  *
    440  * @param key  Array containing the source phone hash as the only item.
    441  * @param keys Expected 1 but ignored.
    442  * @param item Connection hash table item.
    443  *
    444  * @return True on match, false otherwise.
    445  *
    446  */
    447 static int conn_compare(unsigned long key[], hash_count_t keys, link_t *item)
    448 {
    449         assert(key);
    450         assert(item);
    451        
    452         connection_t *conn = hash_table_get_instance(item, connection_t, link);
    453         return (key[0] == conn->in_phone_hash);
    454 }
    455 
    456 static void conn_remove(link_t *item)
    457 {
    458 }
     429static size_t conn_key_hash(void *key)
     430{
     431        sysarg_t in_phone_hash  = *(sysarg_t*)key;
     432        return in_phone_hash ;
     433}
     434
     435static size_t conn_hash(const ht_link_t *item)
     436{
     437        connection_t *conn = hash_table_get_inst(item, connection_t, link);
     438        return conn_key_hash(&conn->in_phone_hash);
     439}
     440
     441static bool conn_key_equal(void *key, const ht_link_t *item)
     442{
     443        sysarg_t in_phone_hash = *(sysarg_t*)key;
     444        connection_t *conn = hash_table_get_inst(item, connection_t, link);
     445        return (in_phone_hash == conn->in_phone_hash);
     446}
     447
    459448
    460449/** Operations for the connection hash table. */
    461 static hash_table_operations_t conn_hash_table_ops = {
     450static hash_table_ops_t conn_hash_table_ops = {
    462451        .hash = conn_hash,
    463         .compare = conn_compare,
    464         .remove_callback = conn_remove
     452        .key_hash = conn_key_hash,
     453        .key_equal = conn_key_equal,
     454        .equal = NULL,
     455        .remove_callback = NULL
    465456};
    466457
    … …  
    510501        futex_down(&async_futex);
    511502       
    512         unsigned long key = call->in_phone_hash;
    513         link_t *hlp = hash_table_find(&conn_hash_table, &key);
     503        ht_link_t *hlp = hash_table_find(&conn_hash_table, &call->in_phone_hash);
    514504       
    515505        if (!hlp) {
    … …  
    518508        }
    519509       
    520         connection_t *conn = hash_table_get_instance(hlp, connection_t, link);
     510        connection_t *conn = hash_table_get_inst(hlp, connection_t, link);
    521511       
    522512        msg_t *msg = malloc(sizeof(*msg));
    … …  
    698688static client_t *async_client_get(task_id_t client_id, bool create)
    699689{
    700         unsigned long key[2] = {
    701                 LOWER32(client_id),
    702                 UPPER32(client_id),
    703         };
    704690        client_t *client = NULL;
    705691
    706692        futex_down(&async_futex);
    707         link_t *lnk = hash_table_find(&client_hash_table, key);
     693        ht_link_t *lnk = hash_table_find(&client_hash_table, &client_id);
    708694        if (lnk) {
    709                 client = hash_table_get_instance(lnk, client_t, link);
     695                client = hash_table_get_inst(lnk, client_t, link);
    710696                atomic_inc(&client->refcnt);
    711697        } else if (create) {
    … …  
    716702               
    717703                        atomic_set(&client->refcnt, 1);
    718                         hash_table_insert(&client_hash_table, key, &client->link);
     704                        hash_table_insert(&client_hash_table, &client->link);
    719705                }
    720706        }
    … …  
    727713{
    728714        bool destroy;
    729         unsigned long key[2] = {
    730                 LOWER32(client->in_task_id),
    731                 UPPER32(client->in_task_id)
    732         };
    733        
     715
    734716        futex_down(&async_futex);
    735717       
    736718        if (atomic_predec(&client->refcnt) == 0) {
    737                 hash_table_remove(&client_hash_table, key, 2);
     719                hash_table_remove(&client_hash_table, &client->in_task_id);
    738720                destroy = true;
    739721        } else
    … …  
    831813         */
    832814        futex_down(&async_futex);
    833         unsigned long key = fibril_connection->in_phone_hash;
    834         hash_table_remove(&conn_hash_table, &key, 1);
     815        hash_table_remove(&conn_hash_table, &fibril_connection->in_phone_hash);
    835816        futex_up(&async_futex);
    836817       
    … …  
    916897       
    917898        /* Add connection to the connection hash table */
    918         unsigned long key = conn->in_phone_hash;
    919899       
    920900        futex_down(&async_futex);
    921         hash_table_insert(&conn_hash_table, &key, &conn->link);
     901        hash_table_insert(&conn_hash_table, &conn->link);
    922902        futex_up(&async_futex);
    923903       
    … …  
    11111091void __async_init(void)
    11121092{
    1113         if (!hash_table_create(&client_hash_table, CLIENT_HASH_TABLE_BUCKETS,
    1114             2, &client_hash_table_ops))
     1093        if (!hash_table_create(&client_hash_table, 0, 0, &client_hash_table_ops))
    11151094                abort();
    11161095       
    1117         if (!hash_table_create(&conn_hash_table, CONN_HASH_TABLE_BUCKETS,
    1118             1, &conn_hash_table_ops))
     1096        if (!hash_table_create(&conn_hash_table, 0, 0, &conn_hash_table_ops))
    11191097                abort();
    11201098       

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

    rd1ef4a1 r9f4067b6  
    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
    42 typedef unsigned long hash_count_t;
    43 typedef unsigned long hash_index_t;
     45/** Opaque hash table link type. */
     46typedef struct ht_link {
     47        link_t link;
     48} ht_link_t;
    4449
    4550/** Set of operations for hash table. */
    4651typedef 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          *
    54          */
    55         hash_index_t (*hash)(unsigned long key[]);
     52        /** Returns the hash of the key stored in the item (ie its lookup key). */
     53        size_t (*hash)(const ht_link_t *item);
    5654       
    57         /** Hash table item comparison function.
    58          *
    59          * @param key Array of keys that will be compared with item. It is
    60          *            not necessary to pass all keys.
    61          *
    62          * @return True if the keys match, false otherwise.
    63          *
    64          */
    65         int (*compare)(unsigned long key[], hash_count_t keys, link_t *item);
     55        /** Returns the hash of the key. */
     56        size_t (*key_hash)(void *key);
    6657       
     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);
     60
     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.
     65         *
     66         * Must not invoke any mutating functions of the hash table.
    6867         *
    6968         * @param item Item that was removed from the hash table.
    70          *
    7169         */
    72         void (*remove_callback)(link_t *item);
    73 } hash_table_operations_t;
     70        void (*remove_callback)(ht_link_t *item);
     71} hash_table_ops_t;
    7472
    7573/** Hash table structure. */
    7674typedef struct {
    77         list_t *entry;
    78         hash_count_t entries;
    79         hash_count_t max_keys;
    80         hash_table_operations_t *op;
     75        hash_table_ops_t *op;
     76        list_t *bucket;
     77        size_t bucket_cnt;
     78        size_t full_item_cnt;
     79        size_t item_cnt;
     80        size_t max_load;
     81        bool apply_ongoing;
    8182} hash_table_t;
    8283
    83 #define hash_table_get_instance(item, type, member) \
    84     list_get_instance((item), type, member)
     84#define hash_table_get_inst(item, type, member) \
     85        member_to_inst((item), type, member)
    8586
    86 extern bool hash_table_create(hash_table_t *, hash_count_t, hash_count_t,
    87     hash_table_operations_t *);
     87extern bool hash_table_create(hash_table_t *, size_t, size_t,
     88        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
    8894extern void hash_table_clear(hash_table_t *);
    89 extern void hash_table_insert(hash_table_t *, unsigned long [], link_t *);
    90 extern link_t *hash_table_find(hash_table_t *, unsigned long []);
    91 extern void hash_table_remove(hash_table_t *, unsigned long [], hash_count_t);
    92 extern void hash_table_destroy(hash_table_t *);
    93 extern void hash_table_apply(hash_table_t *, void (*)(link_t *, void *),
    94     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 *),
     102        void *);
     103
    95104
    96105#endif

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

    rd1ef4a1 r9f4067b6  
    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
    73104#define assert_link_not_used(link) \
    74105        assert(((link)->prev == NULL) && ((link)->next == NULL))
     106
     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}
    75112
    76113/** Initialize doubly-linked circular list link

  • uspace/lib/c/include/macros.h

    rd1ef4a1 r9f4067b6  
    5252            | ((((uint64_t) (up)) & 0xffffffff) << 32))
    5353
     54#ifndef member_to_inst
     55#define member_to_inst(ptr_member, type, member_identif) \
     56        ((type*) (((void*)(ptr_member)) - ((void*)&(((type*)0)->member_identif))))
     57#endif
     58
     59
    5460#endif
    5561

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

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

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

    rd1ef4a1 r9f4067b6  
    4343#endif
    4444
    45 #include <adt/hash_set.h>
    46 
    47 /**
    48  * Initial size of DB's hash set
    49  */
    50 #define NIC_ADDR_DB_INIT_SIZE   8
    51 /**
    52  * Maximal length of addresses in the DB (in bytes).
    53  */
    54 #define NIC_ADDR_MAX_LENGTH             16
     45#include <adt/hash_table.h>
    5546
    5647/**
    … …  
    5849 */
    5950typedef struct nic_addr_db {
    60         hash_set_t set;
     51        hash_table_t set;
    6152        size_t addr_len;
    6253} nic_addr_db_t;
    6354
    64 /**
    65  * Helper structure for keeping the address in the hash set.
    66  */
    67 typedef struct nic_addr_entry {
    68         link_t item;
    69         size_t addr_len;
    70         uint8_t addr[NIC_ADDR_MAX_LENGTH];
    71 } nic_addr_entry_t;
    7255
    7356extern int nic_addr_db_init(nic_addr_db_t *db, size_t addr_len);
    7457extern void nic_addr_db_clear(nic_addr_db_t *db);
    7558extern void nic_addr_db_destroy(nic_addr_db_t *db);
    76 extern size_t nic_addr_db_count(const nic_addr_db_t *db);
    7759extern int nic_addr_db_insert(nic_addr_db_t *db, const uint8_t *addr);
    7860extern int nic_addr_db_remove(nic_addr_db_t *db, const uint8_t *addr);
    79 extern void nic_addr_db_remove_selected(nic_addr_db_t *db,
    80         int (*func)(const uint8_t *, void *), void *arg);
    8161extern int nic_addr_db_contains(const nic_addr_db_t *db, const uint8_t *addr);
    8262extern void nic_addr_db_foreach(const nic_addr_db_t *db,

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

    rd1ef4a1 r9f4067b6  
    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_addr_db.c

    rd1ef4a1 r9f4067b6  
    3535 * @brief Generic hash-set based database of addresses
    3636 */
     37#include "nic_addr_db.h"
     38#include "libarch/common.h"
    3739#include <assert.h>
    3840#include <stdlib.h>
    … …  
    4042#include <errno.h>
    4143#include <mem.h>
    42 
    43 #include "nic_addr_db.h"
    44 
    45 /**
    46  * Hash set helper function
    47  */
    48 static int nic_addr_equals(const link_t *item1, const link_t *item2)
    49 {
    50         assert(item1 && item2);
    51         size_t addr_len = ((const nic_addr_entry_t *) item1)->addr_len;
    52 
    53         assert(addr_len == ((const nic_addr_entry_t *) item2)->addr_len);
    54 
    55         size_t i;
    56         for (i = 0; i < addr_len; ++i) {
    57                 if (((nic_addr_entry_t *) item1)->addr[i] !=
    58                         ((nic_addr_entry_t *) item2)->addr[i])
    59                         return false;
     44#include <adt/hash_table.h>
     45#include <macros.h>
     46#include <stdint.h>
     47
     48
     49/**
     50 * Helper structure for keeping the address in the hash set.
     51 */
     52typedef struct nic_addr_entry {
     53        ht_link_t link;
     54        uint8_t len;
     55        uint8_t addr[1];
     56} nic_addr_entry_t;
     57
     58
     59/*
     60 * Hash table helper functions
     61 */
     62typedef struct {
     63        size_t len;
     64        const uint8_t *addr;
     65} addr_key_t;
     66
     67static bool nic_addr_key_equal(void *key_arg, const ht_link_t *item)
     68{
     69        addr_key_t *key = (addr_key_t*)key_arg;
     70        nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link);
     71       
     72        return 0 == bcmp(entry->addr, key->addr, entry->len);
     73}
     74
     75static size_t addr_hash(size_t len, const uint8_t *addr)
     76{
     77        size_t hash = 0;
     78       
     79        for (size_t i = 0; i < len; ++i) {
     80                hash = (hash << 5) ^ addr[i];
    6081        }
    61         return true;
    62 }
    63 
    64 /**
    65  * Hash set helper function
    66  */
    67 static unsigned long nic_addr_hash(const link_t *item)
    68 {
    69         assert(item);
    70         const nic_addr_entry_t *entry = (const nic_addr_entry_t *) item;
    71         unsigned long hash = 0;
    72 
    73         size_t i;
    74         for (i = 0; i < entry->addr_len; ++i) {
    75                 hash = (hash << 8) ^ (hash >> 24) ^ entry->addr[i];
    76         }
     82       
    7783        return hash;
    7884}
    7985
    80 /**
    81  * Helper wrapper
    82  */
    83 static void nic_addr_destroy(link_t *item, void *unused)
    84 {
    85         free(item);
    86 }
     86static size_t nic_addr_key_hash(void *k)
     87{
     88        addr_key_t *key = (addr_key_t*)k;
     89        return addr_hash(key->len, key->addr);
     90}
     91
     92static size_t nic_addr_hash(const ht_link_t *item)
     93{
     94        nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link);
     95        return addr_hash(entry->len, entry->addr);
     96}
     97
     98static void nic_addr_removed(ht_link_t *item)
     99{
     100        nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link);
     101       
     102        free(entry);
     103}
     104
     105static hash_table_ops_t set_ops = {
     106        .hash = nic_addr_hash,
     107        .key_hash = nic_addr_key_hash,
     108        .key_equal = nic_addr_key_equal,
     109        .equal = NULL,
     110        .remove_callback = nic_addr_removed
     111};
    87112
    88113/**
    … …  
    99124{
    100125        assert(db);
    101         if (addr_len > NIC_ADDR_MAX_LENGTH) {
     126       
     127        if (addr_len > UCHAR_MAX)
    102128                return EINVAL;
    103         }
    104         if (!hash_set_init(&db->set, nic_addr_hash, nic_addr_equals,
    105                 NIC_ADDR_DB_INIT_SIZE)) {
     129       
     130        if (!hash_table_create(&db->set, 0, 0, &set_ops))
    106131                return ENOMEM;
    107         }
     132       
    108133        db->addr_len = addr_len;
    109134        return EOK;
    … …  
    118143{
    119144        assert(db);
    120         hash_set_clear(&db->set, nic_addr_destroy, NULL);
     145        hash_table_clear(&db->set);
    121146}
    122147
    … …  
    129154{
    130155        assert(db);
    131         hash_set_apply(&db->set, nic_addr_destroy, NULL);
    132         hash_set_destroy(&db->set);
    133 }
    134 
    135 /**
    136  * Get number of addresses in the db
    137  *
    138  * @param       db
    139  *
    140  * @return Number of adresses
    141  */
    142 size_t nic_addr_db_count(const nic_addr_db_t *db)
    143 {
    144         assert(db);
    145         return hash_set_count(&db->set);
    146 }
     156        hash_table_destroy(&db->set);
     157}
     158
    147159
    148160/**
    … …  
    160172{
    161173        assert(db && addr);
    162         nic_addr_entry_t *entry = malloc(sizeof (nic_addr_entry_t));
    163         if (entry == NULL) {
     174
     175        addr_key_t key = {
     176                .len = db->addr_len,
     177                .addr = addr
     178        };
     179       
     180        if (hash_table_find(&db->set, &key))
     181                return EEXIST;
     182       
     183        nic_addr_entry_t *entry = malloc(sizeof(nic_addr_entry_t) + db->addr_len - 1);
     184        if (entry == NULL)
    164185                return ENOMEM;
    165         }
    166         entry->addr_len = db->addr_len;
     186
     187        entry->len = (uint8_t) db->addr_len;
    167188        memcpy(entry->addr, addr, db->addr_len);
    168 
    169         return hash_set_insert(&db->set, &entry->item) ? EOK : EEXIST;
     189       
     190        hash_table_insert(&db->set, &entry->link);
     191        return EOK;
    170192}
    171193
    … …  
    182204{
    183205        assert(db && addr);
    184         nic_addr_entry_t entry;
    185         entry.addr_len = db->addr_len;
    186         memcpy(entry.addr, addr, db->addr_len);
    187 
    188         link_t *removed = hash_set_remove(&db->set, &entry.item);
    189         free(removed);
    190         return removed != NULL ? EOK : ENOENT;
     206       
     207        addr_key_t key = {
     208                .len = db->addr_len,
     209                .addr = addr
     210        };
     211       
     212        if (hash_table_remove(&db->set, &key))
     213                return EOK;
     214        else
     215                return ENOENT;
    191216}
    192217
    … …  
    202227{
    203228        assert(db && addr);
    204         nic_addr_entry_t entry;
    205         entry.addr_len = db->addr_len;
    206         memcpy(entry.addr, addr, db->addr_len);
    207 
    208         return hash_set_contains(&db->set, &entry.item);
     229       
     230        addr_key_t key = {
     231                .len = db->addr_len,
     232                .addr = addr
     233        };
     234       
     235        return 0 != hash_table_find(&db->set, &key);
    209236}
    210237
    … …  
    220247 * Helper function for nic_addr_db_foreach
    221248 */
    222 static void nic_addr_db_fe_helper(link_t *item, void *arg) {
     249static bool nic_addr_db_fe_helper(ht_link_t *item, void *arg)
     250{
    223251        nic_addr_db_fe_arg_t *hs = (nic_addr_db_fe_arg_t *) arg;
    224         hs->func(((nic_addr_entry_t *) item)->addr, hs->arg);
     252        nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link);
     253        hs->func(entry->addr, hs->arg);
     254        return true;
    225255}
    226256
    … …  
    237267{
    238268        nic_addr_db_fe_arg_t hs = { .func = func, .arg = arg };
    239         hash_set_apply((hash_set_t *) &db->set, nic_addr_db_fe_helper, &hs);
    240 }
    241 
    242 /**
    243  * Helper structure for nic_addr_db_remove_selected
    244  */
    245 typedef struct {
    246         int (*func)(const uint8_t *, void *);
    247         void *arg;
    248 } nic_addr_db_rs_arg_t;
    249 
    250 /**
    251  * Helper function for nic_addr_db_foreach
    252  */
    253 static int nic_addr_db_rs_helper(link_t *item, void *arg) {
    254         nic_addr_db_rs_arg_t *hs = (nic_addr_db_rs_arg_t *) arg;
    255         int retval = hs->func(((nic_addr_entry_t *) item)->addr, hs->arg);
    256         if (retval) {
    257                 free(item);
    258         }
    259         return retval;
    260 }
    261 
    262 /**
    263  * Removes all addresses for which the function returns non-zero.
    264  *
    265  * @param       db
    266  * @param       func    User-defined function
    267  * @param       arg             Custom argument passed to the function
    268  */
    269 void nic_addr_db_remove_selected(nic_addr_db_t *db,
    270         int (*func)(const uint8_t *, void *), void *arg)
    271 {
    272         nic_addr_db_rs_arg_t hs = { .func = func, .arg = arg };
    273         hash_set_remove_selected(&db->set, nic_addr_db_rs_helper, &hs);
     269        hash_table_apply((hash_table_t*)&db->set, nic_addr_db_fe_helper, &hs);
    274270}
    275271

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

    rd1ef4a1 r9f4067b6  
    3737
    3838#include "nic_wol_virtues.h"
     39#include "nic.h"
    3940#include <assert.h>
    4041#include <errno.h>
    4142
    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)
     43
     44/*
     45 * Hash table helper functions
     46 */
     47
     48static size_t nic_wv_key_hash(void *key)
     49{
     50        return *(nic_wv_id_t*) key;
     51}
     52
     53static size_t nic_wv_hash(const ht_link_t *item)
    4954{
    5055        nic_wol_virtue_t *virtue = (nic_wol_virtue_t *) item;
    51         return (virtue->id == (nic_wv_id_t) key[0]);
    52 }
    53 
    54 /**
    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;
     56        return virtue->id;
     57}
     58
     59static bool nic_wv_key_equal(void *key, const ht_link_t *item)
     60{
     61        nic_wol_virtue_t *virtue = (nic_wol_virtue_t *) item;
     62        return (virtue->id == *(nic_wv_id_t*) key);
    6763}
    6864
    … …  
    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.key_equal = nic_wv_key_equal;
     79        wvs->table_operations.equal = 0;
     80        wvs->table_operations.remove_callback = 0;
     81       
     82        if (!hash_table_create(&wvs->table, 0, 0, &wvs->table_operations)) {
    8583                return ENOMEM;
    8684        }
    … …  
    170168        do {
    171169                virtue->id = wvs->next_id++;
    172         } while (NULL !=
    173                 hash_table_find(&wvs->table, (unsigned long *) &virtue->id));
    174         hash_table_insert(&wvs->table,
    175                 (unsigned long *) &virtue->id, &virtue->item);
     170        } while (NULL != hash_table_find(&wvs->table, &virtue->id));
     171        hash_table_insert(&wvs->table, &virtue->item);
    176172        virtue->next = wvs->lists[virtue->type];
    177173        wvs->lists[virtue->type] = virtue;
    … …  
    191187nic_wol_virtue_t *nic_wol_virtues_remove(nic_wol_virtues_t *wvs, nic_wv_id_t id)
    192188{
    193         nic_wol_virtue_t *virtue = (nic_wol_virtue_t *)
    194                 hash_table_find(&wvs->table, (unsigned long *) &id);
     189        nic_wol_virtue_t *virtue =
     190                (nic_wol_virtue_t *) hash_table_find(&wvs->table, &id);
    195191        if (virtue == NULL) {
    196192                return NULL;
    … …  
    198194
    199195        /* Remove from filter_table */
    200         hash_table_remove(&wvs->table, (unsigned long *) &id, 1);
     196        hash_table_remove_item(&wvs->table, &virtue->item);
    201197
    202198        /* Remove from filter_types */
    … …  
    235231         * constant virtue the retyping is correct.
    236232         */
    237         link_t *virtue = hash_table_find(
    238                 &((nic_wol_virtues_t *) wvs)->table, (unsigned long *) &id);
     233        ht_link_t *virtue = hash_table_find(&((nic_wol_virtues_t *) wvs)->table, &id);
    239234        return (const nic_wol_virtue_t *) virtue;
    240235}
Note: See TracChangeset for help on using the changeset viewer.