Changeset bc216a0 in mainline for uspace/lib

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

Files:

• block/libblock.c (modified) (11 diffs)
• block/libblock.h (modified) (1 diff)
• c/generic/adt/hash_table.c (modified) (14 diffs)
• c/generic/async.c (modified) (12 diffs)
• c/include/adt/hash.h (added)
• c/include/adt/hash_table.h (modified) (3 diffs)
• c/include/adt/list.h (modified) (1 diff)
• nic/include/nic.h (modified) (2 diffs)
• nic/src/nic_addr_db.c (modified) (12 diffs)
• nic/src/nic_wol_virtues.c (modified) (7 diffs)

uspace/lib/block/libblock.c

@@ -254 +254 @@
 }
 
-static size_t cache_key_hash(unsigned long *key)
-{
-        /* As recommended by Effective Java, 2nd Edition. */
-        size_t hash = 17;
-        hash = 31 * hash + key[1];
-        hash = 31 * hash + key[0];
-        return hash;
-}
-
-static size_t cache_hash(const link_t *item)
-{
-        block_t *b = hash_table_get_instance(item, block_t, hash_link);
-        unsigned long key[] = {
-                LOWER32(b->lba),
-                UPPER32(b->lba)
-        };
-        
-        return cache_key_hash(key);
-}
-
-static bool cache_match(unsigned long *key, size_t keys, const link_t *item)
-{
-        block_t *b = hash_table_get_instance(item, block_t, hash_link);
-        return b->lba == MERGE_LOUP32(key[0], key[1]);
+static size_t cache_key_hash(void *key)
+{
+        aoff64_t *lba = (aoff64_t*)key;
+        return *lba;
+}
+
+static size_t cache_hash(const ht_link_t *item)
+{
+        block_t *b = hash_table_get_inst(item, block_t, hash_link);
+        return b->lba;
+}
+
+static bool cache_key_equal(void *key, const ht_link_t *item)
+{
+        aoff64_t *lba = (aoff64_t*)key;
+        block_t *b = hash_table_get_inst(item, block_t, hash_link);
+        return b->lba == *lba;
 }
 
@@ -284 +277 @@
         .hash = cache_hash,
         .key_hash = cache_key_hash,
-        .match = cache_match,
+        .key_equal = cache_key_equal,
         .equal = 0,
         .remove_callback = 0
@@ -317 +310 @@
         cache->blocks_cluster = cache->lblock_size / devcon->pblock_size;
 
-        if (!hash_table_create(&cache->block_hash, 0, 2, &cache_ops)) {
+        if (!hash_table_create(&cache->block_hash, 0, 0, &cache_ops)) {
                 free(cache);
                 return ENOMEM;
@@ -355 +348 @@
                 }
 
-                unsigned long key[2] = {
-                        LOWER32(b->lba),
-                        UPPER32(b->lba)
-                };
-                hash_table_remove(&cache->block_hash, key, 2);
+                hash_table_remove_item(&cache->block_hash, &b->hash_link);
                 
                 free(b->data);
@@ -391 +380 @@
         fibril_rwlock_initialize(&b->contents_lock);
         link_initialize(&b->free_link);
-        link_initialize(&b->hash_link);
 }
 
@@ -411 +399 @@
         cache_t *cache;
         block_t *b;
-        link_t *l;
-        unsigned long key[2] = {
-                LOWER32(ba),
-                UPPER32(ba)
-        };
+        link_t *link;
 
         int rc;
@@ -431 +415 @@
 
         fibril_mutex_lock(&cache->lock);
-        l = hash_table_find(&cache->block_hash, key);
-        if (l) {
+        ht_link_t *hlink = hash_table_find(&cache->block_hash, &ba);
+        if (hlink) {
 found:
                 /*
                  * We found the block in the cache.
                  */
-                b = hash_table_get_instance(l, block_t, hash_link);
+                b = hash_table_get_inst(hlink, block_t, hash_link);
                 fibril_mutex_lock(&b->lock);
                 if (b->refcnt++ == 0)
@@ -475 +459 @@
                                 goto out;
                         }
-                        l = list_first(&cache->free_list);
-                        b = list_get_instance(l, block_t, free_link);
+                        link = list_first(&cache->free_list);
+                        b = list_get_instance(link, block_t, free_link);
 
                         fibril_mutex_lock(&b->lock);
@@ -516 +500 @@
                                         goto retry;
                                 }
-                                l = hash_table_find(&cache->block_hash, key);
-                                if (l) {
+                                hlink = hash_table_find(&cache->block_hash, &ba);
+                                if (hlink) {
                                         /*
                                          * Someone else must have already
@@ -539 +523 @@
                          */
                         list_remove(&b->free_link);
-                        unsigned long temp_key[2] = {
-                                LOWER32(b->lba),
-                                UPPER32(b->lba)
-                        };
-                        hash_table_remove(&cache->block_hash, temp_key, 2);
+                        hash_table_remove_item(&cache->block_hash, &b->hash_link);
                 }
 
@@ -663 +643 @@
                          * Take the block out of the cache and free it.
                          */
-                        unsigned long key[2] = {
-                                LOWER32(block->lba),
-                                UPPER32(block->lba)
-                        };
-                        hash_table_remove(&cache->block_hash, key, 2);
+                        hash_table_remove_item(&cache->block_hash, &block->hash_link);
                         fibril_mutex_unlock(&block->lock);
                         free(block->data);

uspace/lib/block/libblock.h

@@ -84 +84 @@
         link_t free_link;
         /** Link for placing the block into the block hash table. */ 
-        link_t hash_link;
+        ht_link_t hash_link;
         /** Buffer with the block data. */
         void *data;

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

@@ -1 +1 @@
 /*
  * Copyright (c) 2008 Jakub Jermar
+ * Copyright (c) 2012 Adam Hraska
+ * 
  * All rights reserved.
  *
@@ -62 +64 @@
 static size_t round_up_size(size_t size);
 static bool alloc_table(size_t bucket_cnt, list_t **pbuckets);
-static void item_inserted(hash_table_t *h);
-static void item_removed(hash_table_t *h);
-static inline void remove_item(hash_table_t *h, link_t *item);
-static size_t remove_duplicates(hash_table_t *h, unsigned long key[]);
-static size_t remove_matching(hash_table_t *h, unsigned long key[], size_t key_cnt);
+static void clear_items(hash_table_t *h);
+static void resize(hash_table_t *h, size_t new_bucket_cnt);
+static void grow_if_needed(hash_table_t *h);
+static void shrink_if_needed(hash_table_t *h);
 
 /* Dummy do nothing callback to invoke in place of remove_callback == NULL. */
-static void nop_remove_callback(link_t *item)
+static void nop_remove_callback(ht_link_t *item)
 {
         /* no-op */
@@ -90 +91 @@
  *
  */
-bool hash_table_create(hash_table_t *h, size_t init_size, size_t max_keys,
+bool hash_table_create(hash_table_t *h, size_t init_size, size_t max_load,
     hash_table_ops_t *op)
 {
         assert(h);
-        assert(op && op->hash && op->key_hash && op->match);
-        assert(max_keys > 0);
+        assert(op && op->hash && op->key_hash && op->key_equal);
+        
+        /* Check for compulsory ops. */
+        if (!op || !op->hash || !op->key_hash || !op->key_equal)
+                return false;
         
         h->bucket_cnt = round_up_size(init_size);
@@ -102 +106 @@
                 return false;
         
-        h->max_keys = max_keys;
-        h->items = 0;
+        h->max_load = (max_load == 0) ? HT_MAX_LOAD : max_load;
+        h->item_cnt = 0;
         h->op = op;
-        
-        if (h->op->remove_callback == 0) 
+        h->full_item_cnt = h->max_load * h->bucket_cnt;
+        h->apply_ongoing = false;
+
+        if (h->op->remove_callback == 0) {
                 h->op->remove_callback = nop_remove_callback;
+        }
         
         return true;
 }
 
+/** Destroy a hash table instance.
+ *
+ * @param h Hash table to be destroyed.
+ *
+ */
+void hash_table_destroy(hash_table_t *h)
+{
+        assert(h && h->bucket);
+        assert(!h->apply_ongoing);
+        
+        clear_items(h);
+        
+        free(h->bucket);
+
+        h->bucket = 0;
+        h->bucket_cnt = 0;
+}
+
+/** Returns true if there are no items in the table. */
+bool hash_table_empty(hash_table_t *h)
+{
+        assert(h && h->bucket);
+        return h->item_cnt == 0;
+}
+
+/** Returns the number of items in the table. */
+size_t hash_table_size(hash_table_t *h)
+{
+        assert(h && h->bucket);
+        return h->item_cnt;
+}
+
 /** Remove all elements from the hash table
  *
@@ -118 +157 @@
 void hash_table_clear(hash_table_t *h)
 {
+        assert(h && h->bucket);
+        assert(!h->apply_ongoing);
+        
+        clear_items(h);
+        
+        /* Shrink the table to its minimum size if possible. */
+        if (HT_MIN_BUCKETS < h->bucket_cnt) {
+                resize(h, HT_MIN_BUCKETS);
+        }
+}
+
+/** Unlinks and removes all items but does not resize. */
+static void clear_items(hash_table_t *h)
+{
+        if (h->item_cnt == 0)
+                return;
+        
         for (size_t idx = 0; idx < h->bucket_cnt; ++idx) {
                 list_foreach_safe(h->bucket[idx], cur, next) {
+                        assert(cur);
+                        ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link);
+                        
                         list_remove(cur);
-                        h->op->remove_callback(cur);
-                }
-        }
-        
-        h->items = 0;
-
-        /* Shrink the table to its minimum size if possible. */
-        if (HT_MIN_BUCKETS < h->bucket_cnt) {
-                list_t *new_buckets;
-                if (alloc_table(HT_MIN_BUCKETS, &new_buckets)) {
-                        free(h->bucket);
-                        h->bucket = new_buckets;
-                        h->bucket_cnt = HT_MIN_BUCKETS;
-                }
-        }
-}
-
-/** Destroy a hash table instance.
- *
- * @param h Hash table to be destroyed.
- *
- */
-void hash_table_destroy(hash_table_t *h)
-{
-        assert(h);
-        assert(h->bucket);
-        
-        free(h->bucket);
-
-        h->bucket = 0;
-        h->bucket_cnt = 0;
+                        h->op->remove_callback(cur_link);
+                }
+        }
+        
+        h->item_cnt = 0;
 }
 
@@ -160 +193 @@
  * @param item Item to be inserted into the hash table.
  */
-void hash_table_insert(hash_table_t *h, link_t *item)
+void hash_table_insert(hash_table_t *h, ht_link_t *item)
 {
         assert(item);
         assert(h && h->bucket);
-        assert(h->op && h->op->hash);
+        assert(!h->apply_ongoing);
         
         size_t idx = h->op->hash(item) % h->bucket_cnt;
         
-        assert(idx < h->bucket_cnt);
-        
-        list_append(item, &h->bucket[idx]);
-        item_inserted(h);
+        list_append(&item->link, &h->bucket[idx]);
+        ++h->item_cnt;
+        grow_if_needed(h);
 }
 
@@ -184 +216 @@
  * @return True if the inserted item was the only item with such a lookup key.
  */
-bool hash_table_insert_unique(hash_table_t *h, link_t *item)
+bool hash_table_insert_unique(hash_table_t *h, ht_link_t *item)
 {
         assert(item);
         assert(h && h->bucket && h->bucket_cnt);
         assert(h->op && h->op->hash && h->op->equal);
-        
-        size_t item_hash = h->op->hash(item);
-        size_t idx = item_hash % h->bucket_cnt;
-        
-        assert(idx < h->bucket_cnt);
+        assert(!h->apply_ongoing);
+        
+        size_t idx = h->op->hash(item) % h->bucket_cnt;
         
         /* Check for duplicates. */
@@ -201 +231 @@
                  * calling equal() might very well be just as fast.
                  */
-                if (h->op->equal(cur, item))
+                ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link);
+                if (h->op->equal(cur_link, item))
                         return false;
         }
         
-        list_append(item, &h->bucket[idx]);
-        item_inserted(h);
+        list_append(&item->link, &h->bucket[idx]);
+        ++h->item_cnt;
+        grow_if_needed(h);
         
         return true;
@@ -219 +251 @@
  *
  */
-link_t *hash_table_find(const hash_table_t *h, unsigned long key[])
-{
-        assert(h && h->bucket);
-        assert(h->op && h->op->key_hash && h->op->match);
-        
-        size_t key_hash = h->op->key_hash(key);
-        size_t idx = key_hash % h->bucket_cnt;
-
-        assert(idx < h->bucket_cnt);
-        
+ht_link_t *hash_table_find(const hash_table_t *h, void *key)
+{
+        assert(h && h->bucket);
+        
+        size_t idx = h->op->key_hash(key) % h->bucket_cnt;
+
         list_foreach(h->bucket[idx], cur) {
+                ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link);
                 /* 
                  * Is this is the item we are looking for? We could have first 
-                 * checked if the hashes match but op->match() may very well be 
+                 * checked if the hashes match but op->key_equal() may very well be 
                  * just as fast as op->hash().
                  */
-                if (h->op->match(key, h->max_keys, cur)) {
-                        return cur;
+                if (h->op->key_equal(key, cur_link)) {
+                        return cur_link;
                 }
         }
@@ -243 +272 @@
 }
 
-
-/** Apply function to all items in hash table.
- *
- * @param h   Hash table.
- * @param f   Function to be applied. Return false if no more items 
- *            should be visited. The functor must not delete the successor
- *            of the item passed in the first argument.
- * @param arg Argument to be passed to the function.
- *
- */
-void hash_table_apply(hash_table_t *h, bool (*f)(link_t *, void *), void *arg)
-{       
-        for (size_t idx = 0; idx < h->bucket_cnt; ++idx) {
-                list_foreach_safe(h->bucket[idx], cur, next) {
-                        /* 
-                         * The next pointer had already been saved. f() may safely 
-                         * delete cur (but not next!).
-                         */
-                        if (!f(cur, arg))
-                                return;
-                }
-        }
+/** Find the next item equal to item. */
+ht_link_t *hash_table_find_next(const hash_table_t *h, ht_link_t *item)
+{
+        assert(item);
+        assert(h && h->bucket);
+
+        /* Traverse the circular list until we reach the starting item again. */
+        for (link_t *cur = item->link.next; cur != &item->link; cur = cur->next) {
+                assert(cur);
+                ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link);
+                /* 
+                 * Is this is the item we are looking for? We could have first 
+                 * checked if the hashes match but op->equal() may very well be 
+                 * just as fast as op->hash().
+                 */
+                if (h->op->equal(cur_link, item)) {
+                        return cur_link;
+                }
+        }
+
+        return NULL;
 }
 
@@ -278 +306 @@
  * @return Returns the number of removed items.
  */
-size_t hash_table_remove(hash_table_t *h, unsigned long key[], size_t key_cnt)
-{
-        assert(h && h->bucket);
-        assert(h && h->op && h->op->hash &&
-            h->op->remove_callback);
-        assert(key_cnt <= h->max_keys);
-        
-        /* All keys are known, remove from a specific bucket. */
-        if (key_cnt == h->max_keys) {
-                return remove_duplicates(h, key);
-        } else {
-                /*
-                * Fewer keys were passed.
-                * Any partially matching entries are to be removed.
-                */
-                return remove_matching(h, key, key_cnt);
-        }
+size_t hash_table_remove(hash_table_t *h, void *key)
+{
+        assert(h && h->bucket);
+        assert(!h->apply_ongoing);
+        
+        size_t idx = h->op->key_hash(key) % h->bucket_cnt;
+
+        size_t removed = 0;
+        
+        list_foreach_safe(h->bucket[idx], cur, next) {
+                ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link);
+                
+                if (h->op->key_equal(key, cur_link)) {
+                        ++removed;
+                        list_remove(cur);
+                        h->op->remove_callback(cur_link);
+                }
+        }
+
+        h->item_cnt -= removed;
+        shrink_if_needed(h);
+        
+        return removed;
 }
 
 /** Removes an item already present in the table. The item must be in the table.*/
-void hash_table_remove_item(hash_table_t *h, link_t *item)
+void hash_table_remove_item(hash_table_t *h, ht_link_t *item)
 {
         assert(item);
         assert(h && h->bucket);
-        
-        remove_item(h, item);
-}
-
-/** Unlink the item from a bucket, update statistics and resize if needed. */
-static inline void remove_item(hash_table_t *h, link_t *item)
-{
-        assert(item);
-        
-        list_remove(item);
-        item_removed(h);
+        assert(link_in_use(&item->link));
+
+        list_remove(&item->link);
+        --h->item_cnt;
         h->op->remove_callback(item);
-}
-
-/** Removes all items matching key in the bucket key hashes to. */
-static size_t remove_duplicates(hash_table_t *h, unsigned long key[])
-{
-        assert(h && h->bucket);
-        assert(h->op && h->op->key_hash && h->op->match);
-        
-        size_t key_hash = h->op->key_hash(key);
-        size_t idx = key_hash % h->bucket_cnt;
-
-        assert(idx < h->bucket_cnt);
-        
-        size_t removed = 0;
-        
-        list_foreach_safe(h->bucket[idx], cur, next) {
-                if (h->op->match(key, h->max_keys, cur)) {
-                        ++removed;
-                        remove_item(h, cur);
-                }
-        }
-        
-        return removed;
-}
-
-/** Removes all items in any bucket in the table that match the partial key. */
-static size_t remove_matching(hash_table_t *h, unsigned long key[], 
-        size_t key_cnt)
-{
-        assert(h && h->bucket);
-        assert(key_cnt < h->max_keys);
-        
-        size_t removed = 0;
-        /*
-         * Fewer keys were passed.
-         * Any partially matching entries are to be removed.
-         */
+        shrink_if_needed(h);
+}
+
+/** Apply function to all items in hash table.
+ *
+ * @param h   Hash table.
+ * @param f   Function to be applied. Return false if no more items 
+ *            should be visited. The functor may only delete the supplied
+ *            item. It must not delete the successor of the item passed 
+ *            in the first argument.
+ * @param arg Argument to be passed to the function.
+ */
+void hash_table_apply(hash_table_t *h, bool (*f)(ht_link_t *, void *), void *arg)
+{       
+        assert(f);
+        assert(h && h->bucket);
+        
+        if (h->item_cnt == 0)
+                return;
+        
+        h->apply_ongoing = true;
+        
         for (size_t idx = 0; idx < h->bucket_cnt; ++idx) {
                 list_foreach_safe(h->bucket[idx], cur, next) {
-                        if (h->op->match(key, key_cnt, cur)) {
-                                ++removed;
-                                remove_item(h, cur);
-                        }
-                }
-        }
-        
-        return removed;
-        
+                        ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link);
+                        /* 
+                         * The next pointer had already been saved. f() may safely 
+                         * delete cur (but not next!).
+                         */
+                        if (!f(cur_link, arg))
+                                return;
+                }
+        }
+        
+        h->apply_ongoing = false;
+        
+        shrink_if_needed(h);
+        grow_if_needed(h);
 }
 
@@ -392 +409 @@
 }
 
-/** Allocates and rehashes items to a new table. Frees the old table. */
-static void resize(hash_table_t *h, size_t new_bucket_cnt) 
-{
-        assert(h && h->bucket);
-        
-        list_t *new_buckets;
-
-        /* Leave the table as is if we cannot resize. */
-        if (!alloc_table(new_bucket_cnt, &new_buckets))
-                return;
-        
-        /* Rehash all the items to the new table. */
-        for (size_t old_idx = 0; old_idx < h->bucket_cnt; ++old_idx) {
-                list_foreach_safe(h->bucket[old_idx], cur, next) {
-                        size_t new_idx = h->op->hash(cur) % new_bucket_cnt;
-                        list_remove(cur);
-                        list_append(cur, &new_buckets[new_idx]);
-                }
-        }
-        
-        free(h->bucket);
-        h->bucket = new_buckets;
-        h->bucket_cnt = new_bucket_cnt;
-}
-
-/** Shrinks the table if needed. */
-static void item_removed(hash_table_t *h)
-{
-        --h->items;
-        
-        if (HT_MIN_BUCKETS < h->items && h->items <= HT_MAX_LOAD * h->bucket_cnt / 4) {
+
+/** Shrinks the table if the table is only sparely populated. */
+static inline void shrink_if_needed(hash_table_t *h)
+{
+        if (h->item_cnt <= h->full_item_cnt / 4 && HT_MIN_BUCKETS < h->bucket_cnt) {
                 /* 
                  * Keep the bucket_cnt odd (possibly also prime). 
@@ -432 +423 @@
 }
 
-/** Grows the table if needed. */
-static void item_inserted(hash_table_t *h)
-{
-        ++h->items;
-        
+/** Grows the table if table load exceeds the maximum allowed. */
+static inline void grow_if_needed(hash_table_t *h)
+{
         /* Grow the table if the average bucket load exceeds the maximum. */
-        if (HT_MAX_LOAD * h->bucket_cnt < h->items) {
+        if (h->full_item_cnt < h->item_cnt) {
                 /* Keep the bucket_cnt odd (possibly also prime). */
                 size_t new_bucket_cnt = 2 * h->bucket_cnt + 1;
@@ -445 +434 @@
 }
 
+/** Allocates and rehashes items to a new table. Frees the old table. */
+static void resize(hash_table_t *h, size_t new_bucket_cnt) 
+{
+        assert(h && h->bucket);
+        assert(HT_MIN_BUCKETS <= new_bucket_cnt);
+        
+        /* We are traversing the table and resizing would mess up the buckets. */
+        if (h->apply_ongoing)
+                return;
+        
+        list_t *new_buckets;
+
+        /* Leave the table as is if we cannot resize. */
+        if (!alloc_table(new_bucket_cnt, &new_buckets))
+                return;
+        
+        if (0 < h->item_cnt) {
+                /* Rehash all the items to the new table. */
+                for (size_t old_idx = 0; old_idx < h->bucket_cnt; ++old_idx) {
+                        list_foreach_safe(h->bucket[old_idx], cur, next) {
+                                ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link);
+
+                                size_t new_idx = h->op->hash(cur_link) % new_bucket_cnt;
+                                list_remove(cur);
+                                list_append(cur, &new_buckets[new_idx]);
+                        }
+                }
+        }
+        
+        free(h->bucket);
+        h->bucket = new_buckets;
+        h->bucket_cnt = new_bucket_cnt;
+        h->full_item_cnt = h->max_load * h->bucket_cnt;
+}
+
 
 /** @}

uspace/lib/c/generic/async.c

@@ -202 +202 @@
 /* Client connection data */
 typedef struct {
-        link_t link;
+        ht_link_t link;
         
         task_id_t in_task_id;
@@ -214 +214 @@
         
         /** Hash table link. */
-        link_t link;
+        ht_link_t link;
         
         /** Incoming client task ID. */
@@ -390 +390 @@
 static LIST_INITIALIZE(timeout_list);
 
-static size_t client_key_hash(unsigned long key[])
-{
-        assert(key);
-        /* LOWER32(in_task_id) */
-        return key[0] >> 4;
-}
-
-static size_t client_hash(const link_t *item)
-{
-        client_t *client = hash_table_get_instance(item, client_t, link);
-        
-        unsigned long key[2] = {
-                LOWER32(client->in_task_id),
-                UPPER32(client->in_task_id),
-        };
-
-        return client_key_hash(key);
-}
-
-static bool client_match(unsigned long key[], size_t keys, const link_t *item)
-{
-        assert(key);
-        assert(keys == 2);
-        assert(item);
-        
-        client_t *client = hash_table_get_instance(item, client_t, link);
-        return (key[0] == LOWER32(client->in_task_id) &&
-            (key[1] == UPPER32(client->in_task_id)));
+static size_t client_key_hash(void *k)
+{
+        task_id_t key = *(task_id_t*)k;
+        return key;
+}
+
+static size_t client_hash(const ht_link_t *item)
+{
+        client_t *client = hash_table_get_inst(item, client_t, link);
+        return client_key_hash(&client->in_task_id);
+}
+
+static bool client_key_equal(void *k, const ht_link_t *item)
+{
+        task_id_t key = *(task_id_t*)k;
+        client_t *client = hash_table_get_inst(item, client_t, link);
+        return key == client->in_task_id;
 }
 
@@ -425 +414 @@
         .hash = client_hash,
         .key_hash = client_key_hash,
-        .match = client_match,
+        .key_equal = client_key_equal,
         .equal = 0,
         .remove_callback = 0
@@ -437 +426 @@
  *
  */
-static size_t conn_key_hash(unsigned long key[])
-{
-        assert(key);
-        return key[0] >> 4;
-}
-
-static size_t conn_hash(const link_t *item)
-{
-        connection_t *conn = hash_table_get_instance(item, connection_t, link);
-        unsigned long key = conn->in_phone_hash;
-        return conn_key_hash(&key);
-}
-
-/** Compare hash table item with a key.
- *
- * @param key  Array containing the source phone hash as the only item.
- * @param keys Expected 1 but ignored.
- * @param item Connection hash table item.
- *
- * @return True on match, false otherwise.
- *
- */
-static bool conn_match(unsigned long key[], size_t keys, const link_t *item)
-{
-        assert(key);
-        assert(item);
-        
-        connection_t *conn = hash_table_get_instance(item, connection_t, link);
-        return (key[0] == conn->in_phone_hash);
-}
-
-static bool conn_equal(const link_t *item1, const link_t *item2)
-{
-        connection_t *c1 = hash_table_get_instance(item1, connection_t, link);
-        connection_t *c2 = hash_table_get_instance(item2, connection_t, link);
-        
-        return c1->in_phone_hash == c2->in_phone_hash;
-}
-
-static void conn_remove(link_t *item)
-{
-}
+static size_t conn_key_hash(void *key)
+{
+        sysarg_t in_phone_hash  = *(sysarg_t*)key;
+        return in_phone_hash ;
+}
+
+static size_t conn_hash(const ht_link_t *item)
+{
+        connection_t *conn = hash_table_get_inst(item, connection_t, link);
+        return conn_key_hash(&conn->in_phone_hash);
+}
+
+static bool conn_key_equal(void *key, const ht_link_t *item)
+{
+        sysarg_t in_phone_hash = *(sysarg_t*)key;
+        connection_t *conn = hash_table_get_inst(item, connection_t, link);
+        return (in_phone_hash == conn->in_phone_hash);
+}
+
 
 /** Operations for the connection hash table. */
@@ -484 +450 @@
         .hash = conn_hash,
         .key_hash = conn_key_hash,
-        .match = conn_match,
-        .equal = conn_equal,
-        .remove_callback = conn_remove
+        .key_equal = conn_key_equal,
+        .equal = 0,
+        .remove_callback = 0
 };
 
@@ -534 +500 @@
         futex_down(&async_futex);
         
-        unsigned long key = call->in_phone_hash;
-        link_t *hlp = hash_table_find(&conn_hash_table, &key);
+        ht_link_t *hlp = hash_table_find(&conn_hash_table, &call->in_phone_hash);
         
         if (!hlp) {
@@ -542 +507 @@
         }
         
-        connection_t *conn = hash_table_get_instance(hlp, connection_t, link);
+        connection_t *conn = hash_table_get_inst(hlp, connection_t, link);
         
         msg_t *msg = malloc(sizeof(*msg));
@@ -722 +687 @@
 static client_t *async_client_get(task_id_t client_id, bool create)
 {
-        unsigned long key[2] = {
-                LOWER32(client_id),
-                UPPER32(client_id),
-        };
         client_t *client = NULL;
 
         futex_down(&async_futex);
-        link_t *lnk = hash_table_find(&client_hash_table, key);
+        ht_link_t *lnk = hash_table_find(&client_hash_table, &client_id);
         if (lnk) {
-                client = hash_table_get_instance(lnk, client_t, link);
+                client = hash_table_get_inst(lnk, client_t, link);
                 atomic_inc(&client->refcnt);
         } else if (create) {
@@ -751 +712 @@
 {
         bool destroy;
-        unsigned long key[2] = {
-                LOWER32(client->in_task_id),
-                UPPER32(client->in_task_id)
-        };
-        
+
         futex_down(&async_futex);
         
         if (atomic_predec(&client->refcnt) == 0) {
-                hash_table_remove(&client_hash_table, key, 2);
+                hash_table_remove(&client_hash_table, &client->in_task_id);
                 destroy = true;
         } else
@@ -855 +812 @@
          */
         futex_down(&async_futex);
-        unsigned long key = fibril_connection->in_phone_hash;
-        hash_table_remove(&conn_hash_table, &key, 1);
+        hash_table_remove(&conn_hash_table, &fibril_connection->in_phone_hash);
         futex_up(&async_futex);
         
@@ -1134 +1090 @@
 void __async_init(void)
 {
-        if (!hash_table_create(&client_hash_table, 0, 2, &client_hash_table_ops))
+        if (!hash_table_create(&client_hash_table, 0, 0, &client_hash_table_ops))
                 abort();
         
-        if (!hash_table_create(&conn_hash_table, 0, 1, &conn_hash_table_ops))
+        if (!hash_table_create(&conn_hash_table, 0, 0, &conn_hash_table_ops))
                 abort();
         

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

@@ -1 +1 @@
 /*
  * Copyright (c) 2006 Jakub Jermar
+ * Copyright (c) 2012 Adam Hraska
+ * 
  * All rights reserved.
  *
@@ -39 +41 @@
 #include <unistd.h>
 #include <bool.h>
+#include <macros.h>
 
+/** Opaque hash table link type. */
+typedef struct ht_link {
+        link_t link;
+} ht_link_t;
 
 /** Set of operations for hash table. */
 typedef struct {
-        /** Returns the hash of the key stored in the item.
-         */
-        size_t (*hash)(const link_t *item);
+        /** Returns the hash of the key stored in the item (ie its lookup key). */
+        size_t (*hash)(const ht_link_t *item);
         
-        /** Returns the hash of the key.
-         */
-        size_t (*key_hash)(unsigned long key[]);
+        /** Returns the hash of the key. */
+        size_t (*key_hash)(void *key);
         
-        /** Hash table item match function.
-         *
-         * @param key Array of keys that will be compared with item. It is
-         *            not necessary to pass all keys.
-         *
-         * @return True if the keys match, false otherwise.
-         *
-         */
-        bool (*match)(unsigned long key[], size_t keys, const link_t *item);
+        /** True if the items are equal (have the same lookup keys). */
+        bool (*equal)(const ht_link_t *item1, const ht_link_t *item2);
 
-        /** 
-         */
-        bool (*equal)(const link_t *item1, const link_t *item2);
-        
+        /** Returns true if the key is equal to the item's lookup key. */
+        bool (*key_equal)(void *key, const ht_link_t *item);
+
         /** Hash table item removal callback.
          * 
@@ -71 +68 @@
          * @param item Item that was removed from the hash table.
          */
-        void (*remove_callback)(link_t *item);
+        void (*remove_callback)(ht_link_t *item);
 } hash_table_ops_t;
 
 /** Hash table structure. */
 typedef struct {
+        hash_table_ops_t *op;
         list_t *bucket;
         size_t bucket_cnt;
-        size_t max_keys;
-        size_t items;
-        hash_table_ops_t *op;
+        size_t full_item_cnt;
+        size_t item_cnt;
+        size_t max_load;
+        bool apply_ongoing;
 } hash_table_t;
 
-#define hash_table_get_instance(item, type, member) \
-    list_get_instance((item), type, member)
+#define hash_table_get_inst(item, type, member) \
+        member_to_inst((item), type, member)
 
 extern bool hash_table_create(hash_table_t *, size_t, size_t, 
         hash_table_ops_t *);
+extern void hash_table_destroy(hash_table_t *);
+
+extern bool hash_table_empty(hash_table_t *);
+extern size_t hash_table_size(hash_table_t *);
+
 extern void hash_table_clear(hash_table_t *);
-extern void hash_table_insert(hash_table_t *, link_t *);
-extern bool hash_table_insert_unique(hash_table_t *, link_t *);
-extern link_t *hash_table_find(const hash_table_t *, unsigned long []);
-extern size_t hash_table_remove(hash_table_t *, unsigned long [], size_t);
-extern void hash_table_remove_item(hash_table_t *, link_t *);
-extern void hash_table_destroy(hash_table_t *);
-extern void hash_table_apply(hash_table_t *, bool (*)(link_t *, void *), 
+extern void hash_table_insert(hash_table_t *, ht_link_t *);
+extern bool hash_table_insert_unique(hash_table_t *, ht_link_t *);
+extern ht_link_t *hash_table_find(const hash_table_t *, void *);
+extern ht_link_t *hash_table_find_next(const hash_table_t *, ht_link_t *);
+extern size_t hash_table_remove(hash_table_t *, void *);
+extern void hash_table_remove_item(hash_table_t *, ht_link_t *);
+extern void hash_table_apply(hash_table_t *, bool (*)(ht_link_t *, void *), 
         void *);
 

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

@@ -105 +105 @@
         assert(((link)->prev == NULL) && ((link)->next == NULL))
 
+/** Returns true if the link is definitely part of a list. False if not sure. */
+static inline int link_in_use(link_t *link)
+{
+        return link->prev != NULL && link->next != NULL;
+}
+
 /** Initialize doubly-linked circular list link
  *

uspace/lib/nic/include/nic.h

@@ -40 +40 @@
 
 #include <adt/list.h>
+#include <adt/hash_table.h>
 #include <ddf/driver.h>
 #include <device/hw_res_parsed.h>
@@ -53 +54 @@
  */
 typedef struct nic_wol_virtue {
-        link_t item;
+        ht_link_t item;
         nic_wv_id_t id;
         nic_wv_type_t type;

uspace/lib/nic/src/nic_addr_db.c

@@ -36 +36 @@
  */
 #include "nic_addr_db.h"
+#include "libarch/common.h"
 #include <assert.h>
 #include <stdlib.h>
@@ -43 +44 @@
 #include <adt/hash_table.h>
 #include <macros.h>
-
-/* The key count hash table field is not used. Use this dummy value. */
-#define KEY_CNT 1
-
-/**
- * Maximal length of addresses in the DB (in bytes).
- */
-#define NIC_ADDR_MAX_LENGTH             16
+#include <stdint.h>
+
 
 /**
@@ -56 +51 @@
  */
 typedef struct nic_addr_entry {
-        link_t link;
-        uint8_t addr[NIC_ADDR_MAX_LENGTH];
+        ht_link_t link;
+        uint8_t len;
+        uint8_t addr[1];
 } nic_addr_entry_t;
 
@@ -64 +60 @@
  * Hash table helper functions 
  */
-
-static bool nic_addr_match(unsigned long *key, size_t key_cnt, 
-        const link_t *item)
-{
-        uint8_t *addr = (uint8_t*)key;
-        nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link);
-
-        return 0 == bcmp(entry->addr, addr, NIC_ADDR_MAX_LENGTH);
-}
-
-static size_t nic_addr_key_hash(unsigned long *key)
-{
-        uint8_t *addr = (uint8_t*)key;
+typedef struct {
+        size_t len;
+        const uint8_t *addr;
+} addr_key_t;
+
+static bool nic_addr_key_equal(void *key_arg, const ht_link_t *item)
+{
+        addr_key_t *key = (addr_key_t*)key_arg;
+        nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link);
+        
+        return 0 == bcmp(entry->addr, key->addr, entry->len);
+}
+
+static size_t addr_hash(size_t len, const uint8_t *addr)
+{
         size_t hash = 0;
-
-        for (int i = NIC_ADDR_MAX_LENGTH - 1; i >= 0; --i) {
-                hash = (hash << 8) ^ (hash >> 24) ^ addr[i];
+        
+        for (size_t i = 0; i < len; ++i) {
+                hash = (hash << 5) ^ addr[i];
         }
         
@@ -86 +84 @@
 }
 
-static size_t nic_addr_hash(const link_t *item)
-{
-        nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link);
-        
-        unsigned long *key = (unsigned long*)entry->addr;
-        return nic_addr_key_hash(key);
-}
-
-static void nic_addr_removed(link_t *item)
+static size_t nic_addr_key_hash(void *k)
+{
+        addr_key_t *key = (addr_key_t*)k;
+        return addr_hash(key->len, key->addr);
+}
+
+static size_t nic_addr_hash(const ht_link_t *item)
+{
+        nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link);
+        return addr_hash(entry->len, entry->addr);
+}
+
+static void nic_addr_removed(ht_link_t *item)
 {
         nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link);
@@ -104 +106 @@
         .hash = nic_addr_hash,
         .key_hash = nic_addr_key_hash,
-        .match = nic_addr_match,
+        .key_equal = nic_addr_key_equal,
         .equal = 0,
         .remove_callback = nic_addr_removed
@@ -122 +124 @@
 {
         assert(db);
-        if (addr_len > NIC_ADDR_MAX_LENGTH) {
+        
+        if (addr_len > UCHAR_MAX)
                 return EINVAL;
-        }
-        
-        if (!hash_table_create(&db->set, 0, KEY_CNT, &set_ops))
+        
+        if (!hash_table_create(&db->set, 0, 0, &set_ops))
                 return ENOMEM;
         
@@ -152 +154 @@
 {
         assert(db);
-        nic_addr_db_clear(db);
         hash_table_destroy(&db->set);
 }
@@ -171 +172 @@
 {
         assert(db && addr);
-        /* Ugly type-punning hack. */
-        unsigned long *key = (unsigned long*)addr;
-        
-        if (hash_table_find(&db->set, key))
+
+        addr_key_t key = {
+                .len = db->addr_len,
+                .addr = addr
+        };
+        
+        if (hash_table_find(&db->set, &key))
                 return EEXIST;
         
-        nic_addr_entry_t *entry = malloc(sizeof(nic_addr_entry_t));
+        nic_addr_entry_t *entry = malloc(sizeof(nic_addr_entry_t) + db->addr_len - 1);
         if (entry == NULL) 
                 return ENOMEM;
-        
-        link_initialize(&entry->link);
-        
-        bzero(entry->addr, NIC_ADDR_MAX_LENGTH);
+
+        entry->len = (uint8_t) db->addr_len;
         memcpy(entry->addr, addr, db->addr_len);
         
@@ -202 +204 @@
 {
         assert(db && addr);
-        unsigned long *key = (unsigned long*)addr;
-        
-        link_t *item = hash_table_find(&db->set, key);
-        
-        if (item) {
-                hash_table_remove_item(&db->set, item);
+        
+        addr_key_t key = {
+                .len = db->addr_len,
+                .addr = addr
+        };
+        
+        if (hash_table_remove(&db->set, &key))
                 return EOK;
-        } else {
+        else
                 return ENOENT;
-        }
 }
 
@@ -225 +227 @@
 {
         assert(db && addr);
-        unsigned long *key = (unsigned long*)addr;
-        
-        return 0 != hash_table_find(&db->set, key);
+        
+        addr_key_t key = {
+                .len = db->addr_len,
+                .addr = addr
+        };
+        
+        return 0 != hash_table_find(&db->set, &key);
 }
 
@@ -241 +247 @@
  * Helper function for nic_addr_db_foreach
  */
-static bool nic_addr_db_fe_helper(link_t *item, void *arg) 
+static bool nic_addr_db_fe_helper(ht_link_t *item, void *arg) 
 {
         nic_addr_db_fe_arg_t *hs = (nic_addr_db_fe_arg_t *) arg;

uspace/lib/nic/src/nic_wol_virtues.c

@@ -37 +37 @@
 
 #include "nic_wol_virtues.h"
+#include "nic.h"
 #include <assert.h>
 #include <errno.h>
@@ -45 +46 @@
  */
 
-static size_t nic_wv_key_hash(unsigned long keys[])
-{
-        return keys[0];
-}
-
-static size_t nic_wv_hash(const link_t *item)
+static size_t nic_wv_key_hash(void *key)
+{
+        return *(nic_wv_id_t*) key;
+}
+
+static size_t nic_wv_hash(const ht_link_t *item)
 {
         nic_wol_virtue_t *virtue = (nic_wol_virtue_t *) item;
-        unsigned long key = virtue->id;
-        return nic_wv_key_hash(&key);
-}
-
-static bool nic_wv_match(unsigned long key[], size_t keys, const link_t *item)
+        return virtue->id;
+}
+
+static bool nic_wv_key_equal(void *key, const ht_link_t *item)
 {
         nic_wol_virtue_t *virtue = (nic_wol_virtue_t *) item;
-        return (virtue->id == (nic_wv_id_t) key[0]);
+        return (virtue->id == *(nic_wv_id_t*) key);
 }
 
@@ -76 +76 @@
         wvs->table_operations.hash = nic_wv_hash;
         wvs->table_operations.key_hash = nic_wv_key_hash;
-        wvs->table_operations.match = nic_wv_match;
+        wvs->table_operations.key_equal = nic_wv_key_equal;
         wvs->table_operations.equal = 0;
         wvs->table_operations.remove_callback = 0;
         
-        if (!hash_table_create(&wvs->table, 0, 1, &wvs->table_operations)) {
+        if (!hash_table_create(&wvs->table, 0, 0, &wvs->table_operations)) {
                 return ENOMEM;
         }
@@ -168 +168 @@
         do {
                 virtue->id = wvs->next_id++;
-        } while (NULL !=
-                hash_table_find(&wvs->table, (unsigned long *) &virtue->id));
+        } while (NULL != hash_table_find(&wvs->table, &virtue->id));
         hash_table_insert(&wvs->table, &virtue->item);
         virtue->next = wvs->lists[virtue->type];
@@ -188 +187 @@
 nic_wol_virtue_t *nic_wol_virtues_remove(nic_wol_virtues_t *wvs, nic_wv_id_t id)
 {
-        nic_wol_virtue_t *virtue = (nic_wol_virtue_t *)
-                hash_table_find(&wvs->table, (unsigned long *) &id);
+        nic_wol_virtue_t *virtue = 
+                (nic_wol_virtue_t *) hash_table_find(&wvs->table, &id);
         if (virtue == NULL) {
                 return NULL;
@@ -195 +194 @@
 
         /* Remove from filter_table */
-        hash_table_remove(&wvs->table, (unsigned long *) &id, 1);
+        hash_table_remove_item(&wvs->table, &virtue->item);
 
         /* Remove from filter_types */
@@ -232 +231 @@
          * constant virtue the retyping is correct.
          */
-        link_t *virtue = hash_table_find(
-                &((nic_wol_virtues_t *) wvs)->table, (unsigned long *) &id);
+        ht_link_t *virtue = hash_table_find(&((nic_wol_virtues_t *) wvs)->table, &id);
         return (const nic_wol_virtue_t *) virtue;
 }