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

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

File:
1 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/** @}
Note: See TracChangeset for help on using the changeset viewer.