Ignore:
Timestamp:
2010-04-23T21:42:26Z (14 years ago)
Author:
Jiri Svoboda <jiri@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
6c39a907
Parents:
38aaacc2 (diff), 80badbe (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 mainline changes.

File:
1 edited

Legend:

Unmodified
Added
Removed

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

    r38aaacc2 rf4f866c  
    4242#include <malloc.h>
    4343#include <assert.h>
    44 #include <stdio.h>
    4544#include <str.h>
    4645
    4746/** Create chained hash table.
    4847 *
    49  * @param h             Hash table structure. Will be initialized by this call.
    50  * @param m             Number of hash table buckets.
    51  * @param max_keys      Maximal number of keys needed to identify an item.
    52  * @param op            Hash table operations structure.
    53  * @return              True on success
     48 * @param h        Hash table structure. Will be initialized by this call.
     49 * @param m        Number of hash table buckets.
     50 * @param max_keys Maximal number of keys needed to identify an item.
     51 * @param op       Hash table operations structure.
     52 *
     53 * @return True on success
     54 *
    5455 */
    5556int hash_table_create(hash_table_t *h, hash_count_t m, hash_count_t max_keys,
    5657    hash_table_operations_t *op)
    5758{
    58         hash_count_t i;
    59 
    6059        assert(h);
    6160        assert(op && op->hash && op->compare);
    … …  
    6362       
    6463        h->entry = malloc(m * sizeof(link_t));
    65         if (!h->entry) {
    66                 printf("cannot allocate memory for hash table\n");
     64        if (!h->entry)
    6765                return false;
    68         }
     66       
    6967        memset((void *) h->entry, 0,  m * sizeof(link_t));
    7068       
     69        hash_count_t i;
    7170        for (i = 0; i < m; i++)
    7271                list_initialize(&h->entry[i]);
    … …  
    7574        h->max_keys = max_keys;
    7675        h->op = op;
     76       
    7777        return true;
    7878}
    … …  
    8080/** Destroy a hash table instance.
    8181 *
    82  * @param h             Hash table to be destroyed.
     82 * @param h Hash table to be destroyed.
     83 *
    8384 */
    8485void hash_table_destroy(hash_table_t *h)
    … …  
    8687        assert(h);
    8788        assert(h->entry);
     89       
    8890        free(h->entry);
    8991}
    … …  
    9193/** Insert item into a hash table.
    9294 *
    93  * @param h             Hash table.
    94  * @param key           Array of all keys necessary to compute hash index.
    95  * @param item          Item to be inserted into the hash table.
     95 * @param h    Hash table.
     96 * @param key  Array of all keys necessary to compute hash index.
     97 * @param item Item to be inserted into the hash table.
    9698 */
    9799void hash_table_insert(hash_table_t *h, unsigned long key[], link_t *item)
    98100{
    99         hash_index_t chain;
    100 
    101101        assert(item);
    102102        assert(h && h->op && h->op->hash && h->op->compare);
    103 
    104         chain = h->op->hash(key);
     103       
     104        hash_index_t chain = h->op->hash(key);
    105105        assert(chain < h->entries);
    106106       
    … …  
    110110/** Search hash table for an item matching keys.
    111111 *
    112  * @param h             Hash table.
    113  * @param key           Array of all keys needed to compute hash index.
    114  *
    115  * @return              Matching item on success, NULL if there is no such item.
     112 * @param h   Hash table.
     113 * @param key Array of all keys needed to compute hash index.
     114 *
     115 * @return Matching item on success, NULL if there is no such item.
     116 *
    116117 */
    117118link_t *hash_table_find(hash_table_t *h, unsigned long key[])
    118119{
     120        assert(h && h->op && h->op->hash && h->op->compare);
     121       
     122        hash_index_t chain = h->op->hash(key);
     123        assert(chain < h->entries);
     124       
    119125        link_t *cur;
    120         hash_index_t chain;
    121 
    122         assert(h && h->op && h->op->hash && h->op->compare);
    123 
    124         chain = h->op->hash(key);
    125         assert(chain < h->entries);
    126        
    127126        for (cur = h->entry[chain].next; cur != &h->entry[chain];
    128127            cur = cur->next) {
    … …  
    142141 * For each removed item, h->remove_callback() is called.
    143142 *
    144  * @param h             Hash table.
    145  * @param key           Array of keys that will be compared against items of
    146  *                      the hash table.
    147  * @param keys          Number of keys in the 'key' array.
     143 * @param h    Hash table.
     144 * @param key  Array of keys that will be compared against items of
     145 *             the hash table.
     146 * @param keys Number of keys in the 'key' array.
     147 *
    148148 */
    149149void hash_table_remove(hash_table_t *h, unsigned long key[], hash_count_t keys)
    150150{
    151         hash_index_t chain;
    152         link_t *cur;
    153 
    154151        assert(h && h->op && h->op->hash && h->op->compare &&
    155152            h->op->remove_callback);
    156153        assert(keys <= h->max_keys);
    157154       
     155        link_t *cur;
     156       
    158157        if (keys == h->max_keys) {
    159 
    160158                /*
    161159                 * All keys are known, hash_table_find() can be used to find the
    162160                 * entry.
    163161                 */
    164        
     162               
    165163                cur = hash_table_find(h, key);
    166164                if (cur) {
    … …  
    168166                        h->op->remove_callback(cur);
    169167                }
     168               
    170169                return;
    171170        }
    … …  
    175174         * Any partially matching entries are to be removed.
    176175         */
     176        hash_index_t chain;
    177177        for (chain = 0; chain < h->entries; chain++) {
    178178                for (cur = h->entry[chain].next; cur != &h->entry[chain];
    … …  
    195195/** Apply fucntion to all items in hash table.
    196196 *
    197  * @param h             Hash table.
    198  * @param f             Function to be applied.
    199  * @param arg           Argument to be passed to the function.
    200  */
    201 void
    202 hash_table_apply(hash_table_t *h, void (*f)(link_t *, void *), void *arg)
     197 * @param h   Hash table.
     198 * @param f   Function to be applied.
     199 * @param arg Argument to be passed to the function.
     200 *
     201 */
     202void hash_table_apply(hash_table_t *h, void (*f)(link_t *, void *), void *arg)
    203203{
    204204        hash_index_t bucket;
    205205        link_t *cur;
    206 
     206       
    207207        for (bucket = 0; bucket < h->entries; bucket++) {
    208208                for (cur = h->entry[bucket].next; cur != &h->entry[bucket];
Note: See TracChangeset for help on using the changeset viewer.