Changeset 0ca7286 in mainline for uspace/lib

Timestamp:

2012-07-21T11:19:27Z (14 years ago)

Author:

Adam Hraska <adam.hraska+hos@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

2732c94

Parents:

1c1da4b

Message:

Added resizing to user space (single-threaded) hash_table. Resizes in a way to mitigate effects of bad hash functions. Change of interface affected many files.

Location:

uspace/lib

Files:

• block/libblock.c (modified) (5 diffs)
• c/generic/adt/hash_table.c (modified) (7 diffs)
• c/generic/async.c (modified) (10 diffs)
• c/include/adt/hash_table.h (modified) (3 diffs)
• c/include/adt/list.h (modified) (1 diff)
• nic/include/nic_wol_virtues.h (modified) (1 diff)
• nic/src/nic_wol_virtues.c (modified) (4 diffs)

uspace/lib/block/libblock.c

@@ -62 +62 @@
 static LIST_INITIALIZE(dcl);
 
-#define CACHE_BUCKETS_LOG2  10
-#define CACHE_BUCKETS       (1 << CACHE_BUCKETS_LOG2)
 
 typedef struct {
@@ -256 +254 @@
 }
 
-static hash_index_t cache_hash(unsigned long *key)
-{
-        return MERGE_LOUP32(key[0], key[1]) & (CACHE_BUCKETS - 1);
-}
-
-static int cache_compare(unsigned long *key, hash_count_t keys, link_t *item)
+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);
@@ -267 +280 @@
 }
 
-static void cache_remove_callback(link_t *item)
-{
-}
-
-static hash_table_operations_t cache_ops = {
+
+static hash_table_ops_t cache_ops = {
         .hash = cache_hash,
-        .compare = cache_compare,
-        .remove_callback = cache_remove_callback
+        .key_hash = cache_key_hash,
+        .match = cache_match,
+        .equal = 0,
+        .remove_callback = 0
 };
 
@@ -305 +317 @@
         cache->blocks_cluster = cache->lblock_size / devcon->pblock_size;
 
-        if (!hash_table_create(&cache->block_hash, CACHE_BUCKETS, 2,
-            &cache_ops)) {
+        if (!hash_table_create(&cache->block_hash, 0, 2, &cache_ops)) {
                 free(cache);
                 return ENOMEM;
@@ -540 +551 @@
                 b->lba = ba;
                 b->pba = ba_ltop(devcon, b->lba);
-                hash_table_insert(&cache->block_hash, key, &b->hash_link);
+                hash_table_insert(&cache->block_hash, &b->hash_link);
 
                 /*

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

@@ -34 +34 @@
 
 /*
- * This is an implementation of generic chained hash table.
+ * This is an implementation of a generic resizable chained hash table.
+ * 
+ * The table grows to 2*n+1 buckets each time, starting at n == 89, 
+ * per Thomas Wang's recommendation:
+ * http://www.concentric.net/~Ttwang/tech/hashsize.htm
+ * 
+ * This policy produces prime table sizes for the first five resizes
+ * and generally produces table sizes which are either prime or 
+ * have fairly large (prime/odd) divisors. Having a prime table size
+ * mitigates the use of suboptimal hash functions and distributes
+ * items over the whole table.
  */
 
@@ -44 +54 @@
 #include <str.h>
 
+/* Optimal initial bucket count. See comment above. */
+#define HT_MIN_BUCKETS  89
+/* The table is resized when the average load per bucket exceeds this number. */
+#define HT_MAX_LOAD     2
+
+
+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);
+
+/* Dummy do nothing callback to invoke in place of remove_callback == NULL. */
+static void nop_remove_callback(link_t *item)
+{
+        /* no-op */
+}
+
+
 /** Create chained hash table.
  *
  * @param h        Hash table structure. Will be initialized by this call.
- * @param m        Number of hash table buckets.
+ * @param init_size Initial desired number of hash table buckets. Pass zero
+ *                 if you want the default initial size. 
  * @param max_keys Maximal number of keys needed to identify an item.
- * @param op       Hash table operations structure.
+ * @param op       Hash table operations structure. remove_callback()
+ *                 is optional and can be NULL if no action is to be taken
+ *                 upon removal. equal() is optional if and only if
+ *                 hash_table_insert_unique() will never be invoked.
+ *                 All other operations are mandatory. 
  *
  * @return True on success
  *
  */
-bool hash_table_create(hash_table_t *h, hash_count_t m, hash_count_t max_keys,
-    hash_table_operations_t *op)
+bool hash_table_create(hash_table_t *h, size_t init_size, size_t max_keys,
+    hash_table_ops_t *op)
 {
         assert(h);
-        assert(op && op->hash && op->compare);
+        assert(op && op->hash && op->key_hash && op->match);
         assert(max_keys > 0);
         
-        h->entry = malloc(m * sizeof(list_t));
-        if (!h->entry)
+        h->bucket_cnt = round_up_size(init_size);
+        
+        if (!alloc_table(h->bucket_cnt, &h->bucket))
                 return false;
         
-        memset((void *) h->entry, 0,  m * sizeof(list_t));
-        
-        hash_count_t i;
-        for (i = 0; i < m; i++)
-                list_initialize(&h->entry[i]);
-        
-        h->entries = m;
         h->max_keys = max_keys;
+        h->items = 0;
         h->op = op;
         
+        if (h->op->remove_callback == 0) 
+                h->op->remove_callback = nop_remove_callback;
+        
         return true;
 }
@@ -84 +118 @@
 void hash_table_clear(hash_table_t *h)
 {
-        for (hash_count_t chain = 0; chain < h->entries; ++chain) {
-                link_t *cur;
-                link_t *next;
-                
-                for (cur = h->entry[chain].head.next;
-                    cur != &h->entry[chain].head;
-                    cur = next) {
-                        next = cur->next;
+        for (size_t idx = 0; idx < h->bucket_cnt; ++idx) {
+                list_foreach_safe(h->bucket[idx], cur, next) {
                         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;
+                }
+        }
 }
 
@@ -106 +146 @@
 {
         assert(h);
-        assert(h->entry);
-        
-        free(h->entry);
+        assert(h->bucket);
+        
+        free(h->bucket);
+
+        h->bucket = 0;
+        h->bucket_cnt = 0;
 }
 
@@ -117 +160 @@
  * @param item Item to be inserted into the hash table.
  */
-void hash_table_insert(hash_table_t *h, unsigned long key[], link_t *item)
+void hash_table_insert(hash_table_t *h, link_t *item)
 {
         assert(item);
-        assert(h && h->op && h->op->hash && h->op->compare);
-        
-        hash_index_t chain = h->op->hash(key);
-        assert(chain < h->entries);
-        
-        list_append(item, &h->entry[chain]);
+        assert(h && h->bucket);
+        assert(h->op && h->op->hash);
+        
+        size_t idx = h->op->hash(item) % h->bucket_cnt;
+        
+        assert(idx < h->bucket_cnt);
+        
+        list_append(item, &h->bucket[idx]);
+        item_inserted(h);
+}
+
+
+/** Insert item into a hash table if not already present.
+ *
+ * @param h    Hash table.
+ * @param key  Array of all keys necessary to compute hash index.
+ * @param item Item to be inserted into the hash table.
+ * 
+ * @return False if such an item had already been inserted. 
+ * @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)
+{
+        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);
+        
+        /* Check for duplicates. */
+        list_foreach(h->bucket[idx], cur) {
+                /* 
+                 * We could filter out items using their hashes first, but 
+                 * calling equal() might very well be just as fast.
+                 */
+                if (h->op->equal(cur, item))
+                        return false;
+        }
+        
+        list_append(item, &h->bucket[idx]);
+        item_inserted(h);
+        
+        return true;
 }
 
@@ -138 +221 @@
 link_t *hash_table_find(hash_table_t *h, unsigned long key[])
 {
-        assert(h && h->op && h->op->hash && h->op->compare);
-        
-        hash_index_t chain = h->op->hash(key);
-        assert(chain < h->entries);
-        
-        list_foreach(h->entry[chain], cur) {
-                if (h->op->compare(key, h->max_keys, cur)) {
-                        /*
-                         * The entry is there.
+        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);
+        
+        list_foreach(h->bucket[idx], cur) {
+                /* 
+                 * 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 
+                 * just as fast as op->hash().
+                 */
+                if (h->op->match(key, h->max_keys, cur)) {
+                        return cur;
+                }
+        }
+        
+        return NULL;
+}
+
+
+/** 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!).
                          */
-                        return cur;
-                }
-        }
-        
-        return NULL;
+                        if (!f(cur, arg))
+                                return;
+                }
+        }
 }
 
@@ -163 +275 @@
  *             the hash table.
  * @param keys Number of keys in the 'key' array.
- *
- */
-void hash_table_remove(hash_table_t *h, unsigned long key[], hash_count_t keys)
-{
-        assert(h && h->op && h->op->hash && h->op->compare &&
+ * 
+ * @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(keys <= h->max_keys);
-        
-        if (keys == h->max_keys) {
+        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 {
                 /*
-                 * All keys are known, hash_table_find() can be used to find the
-                 * entry.
-                 */
-                
-                link_t *cur = hash_table_find(h, key);
-                if (cur) {
-                        list_remove(cur);
-                        h->op->remove_callback(cur);
-                }
-                
-                return;
-        }
-        
+                * Fewer keys were passed.
+                * Any partially matching entries are to be removed.
+                */
+                return remove_matching(h, key, key_cnt);
+        }
+}
+
+/** 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)
+{
+        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);
+        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.
          */
-        hash_index_t chain;
-        for (chain = 0; chain < h->entries; chain++) {
-                for (link_t *cur = h->entry[chain].head.next;
-                    cur != &h->entry[chain].head;
-                    cur = cur->next) {
-                        if (h->op->compare(key, keys, cur)) {
-                                link_t *hlp;
-                                
-                                hlp = cur;
-                                cur = cur->prev;
-                                
-                                list_remove(hlp);
-                                h->op->remove_callback(hlp);
-                                
-                                continue;
+        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);
                         }
                 }
         }
-}
-
-/** Apply function to all items in hash table.
- *
- * @param h   Hash table.
- * @param f   Function to be applied.
- * @param arg Argument to be passed to the function.
- *
- */
-void hash_table_apply(hash_table_t *h, void (*f)(link_t *, void *), void *arg)
-{       
-        for (hash_index_t bucket = 0; bucket < h->entries; bucket++) {
-                link_t *cur;
-                link_t *next;
-
-                for (cur = h->entry[bucket].head.next; cur != &h->entry[bucket].head;
-                    cur = next) {
-                        /*
-                         * The next pointer must be stored prior to the functor
-                         * call to allow using destructor as the functor (the
-                         * free function could overwrite the cur->next pointer).
-                         */
-                        next = cur->next;
-                        f(cur, arg);
-                }
-        }
-}
+        
+        return removed;
+        
+}
+
+/** Rounds up size to the nearest suitable table size. */
+static size_t round_up_size(size_t size)
+{
+        size_t rounded_size = HT_MIN_BUCKETS;
+        
+        while (rounded_size < size) {
+                rounded_size = 2 * rounded_size + 1;
+        }
+        
+        return rounded_size;
+}
+
+/** Allocates and initializes the desired number of buckets. True if successful.*/
+static bool alloc_table(size_t bucket_cnt, list_t **pbuckets)
+{
+        assert(pbuckets && HT_MIN_BUCKETS <= bucket_cnt);
+                
+        list_t *buckets = malloc(bucket_cnt * sizeof(list_t));
+        if (!buckets)
+                return false;
+        
+        for (size_t i = 0; i < bucket_cnt; i++)
+                list_initialize(&buckets[i]);
+
+        *pbuckets = buckets;
+        return true;
+}
+
+/** 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) {
+                /* 
+                 * Keep the bucket_cnt odd (possibly also prime). 
+                 * Shrink from 2n + 1 to n. Integer division discards the +1.
+                 */
+                size_t new_bucket_cnt = h->bucket_cnt / 2;
+                resize(h, new_bucket_cnt);
+        }
+}
+
+/** Grows the table if needed. */
+static void item_inserted(hash_table_t *h)
+{
+        ++h->items;
+        
+        /* Grow the table if the average bucket load exceeds the maximum. */
+        if (HT_MAX_LOAD * h->bucket_cnt < h->items) {
+                /* Keep the bucket_cnt odd (possibly also prime). */
+                size_t new_bucket_cnt = 2 * h->bucket_cnt + 1;
+                resize(h, new_bucket_cnt);
+        }
+}
+
 
 /** @}

uspace/lib/c/generic/async.c

@@ -115 +115 @@
 #include <macros.h>
 
-#define CLIENT_HASH_TABLE_BUCKETS  32
-#define CONN_HASH_TABLE_BUCKETS    32
 
 /** Session data */
@@ -392 +390 @@
 static LIST_INITIALIZE(timeout_list);
 
-static hash_index_t client_hash(unsigned long key[])
+static size_t client_key_hash(unsigned long key[])
 {
         assert(key);
-        
-        return (((key[0]) >> 4) % CLIENT_HASH_TABLE_BUCKETS);
-}
-
-static int client_compare(unsigned long key[], hash_count_t keys, link_t *item)
+        /* 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);
@@ -410 +420 @@
 }
 
-static void client_remove(link_t *item)
-{
-}
 
 /** Operations for the client hash table. */
-static hash_table_operations_t client_hash_table_ops = {
+static hash_table_ops_t client_hash_table_ops = {
         .hash = client_hash,
-        .compare = client_compare,
-        .remove_callback = client_remove
+        .key_hash = client_key_hash,
+        .match = client_match,
+        .equal = 0,
+        .remove_callback = 0
 };
 
@@ -428 +437 @@
  *
  */
-static hash_index_t conn_hash(unsigned long key[])
+static size_t conn_key_hash(unsigned long key[])
 {
         assert(key);
-        
-        return (((key[0]) >> 4) % CONN_HASH_TABLE_BUCKETS);
+        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);
 }
 
@@ -444 +459 @@
  *
  */
-static int conn_compare(unsigned long key[], hash_count_t keys, link_t *item)
+static bool conn_match(unsigned long key[], size_t keys, const link_t *item)
 {
         assert(key);
@@ -453 +468 @@
 }
 
+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)
 {
@@ -458 +481 @@
 
 /** Operations for the connection hash table. */
-static hash_table_operations_t conn_hash_table_ops = {
+static hash_table_ops_t conn_hash_table_ops = {
         .hash = conn_hash,
-        .compare = conn_compare,
+        .key_hash = conn_key_hash,
+        .match = conn_match,
+        .equal = conn_equal,
         .remove_callback = conn_remove
 };
@@ -715 +740 @@
                 
                         atomic_set(&client->refcnt, 1);
-                        hash_table_insert(&client_hash_table, key, &client->link);
+                        hash_table_insert(&client_hash_table, &client->link);
                 }
         }
@@ -915 +940 @@
         
         /* Add connection to the connection hash table */
-        unsigned long key = conn->in_phone_hash;
         
         futex_down(&async_futex);
-        hash_table_insert(&conn_hash_table, &key, &conn->link);
+        hash_table_insert(&conn_hash_table, &conn->link);
         futex_up(&async_futex);
         
@@ -1110 +1134 @@
 void __async_init(void)
 {
-        if (!hash_table_create(&client_hash_table, CLIENT_HASH_TABLE_BUCKETS,
-            2, &client_hash_table_ops))
+        if (!hash_table_create(&client_hash_table, 0, 2, &client_hash_table_ops))
                 abort();
         
-        if (!hash_table_create(&conn_hash_table, CONN_HASH_TABLE_BUCKETS,
-            1, &conn_hash_table_ops))
+        if (!hash_table_create(&conn_hash_table, 0, 1, &conn_hash_table_ops))
                 abort();
         

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

@@ -40 +40 @@
 #include <bool.h>
 
-typedef unsigned long hash_count_t;
-typedef unsigned long hash_index_t;
 
 /** Set of operations for hash table. */
 typedef struct {
-        /** Hash function.
-         *
-         * @param key Array of keys needed to compute hash index.
-         *            All keys must be passed.
-         *
-         * @return Index into hash table.
-         *
+        /** Returns the hash of the key stored in the item.
          */
-        hash_index_t (*hash)(unsigned long key[]);
+        size_t (*hash)(const link_t *item);
         
-        /** Hash table item comparison function.
+        /** Returns the hash of the key.
+         */
+        size_t (*key_hash)(unsigned long key[]);
+        
+        /** Hash table item match function.
          *
          * @param key Array of keys that will be compared with item. It is
@@ -63 +59 @@
          *
          */
-        int (*compare)(unsigned long key[], hash_count_t keys, link_t *item);
+        bool (*match)(unsigned long key[], size_t keys, const link_t *item);
+
+        /** 
+         */
+        bool (*equal)(const link_t *item1, const link_t *item2);
         
         /** Hash table item removal callback.
+         * 
+         * Must not invoke any mutating functions of the hash table.
          *
          * @param item Item that was removed from the hash table.
-         *
          */
         void (*remove_callback)(link_t *item);
-} hash_table_operations_t;
+} hash_table_ops_t;
 
 /** Hash table structure. */
 typedef struct {
-        list_t *entry;
-        hash_count_t entries;
-        hash_count_t max_keys;
-        hash_table_operations_t *op;
+        list_t *bucket;
+        size_t bucket_cnt;
+        size_t max_keys;
+        size_t items;
+        hash_table_ops_t *op;
 } hash_table_t;
 
@@ -84 +86 @@
     list_get_instance((item), type, member)
 
-extern bool hash_table_create(hash_table_t *, hash_count_t, hash_count_t,
-    hash_table_operations_t *);
+extern bool hash_table_create(hash_table_t *, size_t, size_t, 
+        hash_table_ops_t *);
 extern void hash_table_clear(hash_table_t *);
-extern void hash_table_insert(hash_table_t *, unsigned long [], link_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(hash_table_t *, unsigned long []);
-extern void hash_table_remove(hash_table_t *, unsigned long [], hash_count_t);
+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 *, void (*)(link_t *, void *),
-    void *);
+extern void hash_table_apply(hash_table_t *, bool (*)(link_t *, void *), 
+        void *);
 
 #endif

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

@@ -71 +71 @@
             iterator != &(list).head; iterator = iterator->next)
 
+/** Unlike list_foreach(), allows removing items while traversing a list.
+ * 
+ * @code
+ * list_t mylist;
+ * typedef struct item {
+ *     int value;
+ *     link_t item_link;
+ * } item_t;
+ * 
+ * //..
+ * 
+ * // Print each list element's value and remove the element from the list.
+ * list_foreach_safe(mylist, cur_link, next_link) {
+ *     item_t *cur_item = list_get_instance(cur_link, item_t, item_link);
+ *     printf("%d\n", cur_item->value);
+ *     list_remove(cur_link);
+ * }
+ * @endcode
+ * 
+ * @param list List to traverse.
+ * @param iterator Iterator to the current element of the list.
+ *             The item this iterator points may be safely removed
+ *             from the list.
+ * @param next_iter Iterator to the next element of the list.
+ */
+#define list_foreach_safe(list, iterator, next_iter) \
+        for (link_t *iterator = (list).head.next, \
+                *next_iter = iterator->next; \
+                iterator != &(list).head; \
+                iterator = next_iter, next_iter = iterator->next)
+
+
 #define assert_link_not_used(link) \
         assert(((link)->prev == NULL) && ((link)->next == NULL))

uspace/lib/nic/include/nic_wol_virtues.h

@@ -51 +51 @@
          * Operations for table
          */
-        hash_table_operations_t table_operations;
+        hash_table_ops_t table_operations;
         /**
          * WOL virtues hashed by their ID's.

uspace/lib/nic/src/nic_wol_virtues.c

@@ -40 +40 @@
 #include <errno.h>
 
-#define NIC_WV_HASH_COUNT 32
-
-/**
- * Hash table helper function
- */
-static int nic_wv_compare(unsigned long key[], hash_count_t keys,
-        link_t *item)
+
+/*
+ * Hash table helper functions
+ */
+
+static size_t nic_wv_key_hash(unsigned long keys[])
+{
+        return keys[0];
+}
+
+static size_t nic_wv_hash(const 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)
 {
         nic_wol_virtue_t *virtue = (nic_wol_virtue_t *) item;
@@ -53 +64 @@
 
 /**
- * Hash table helper function
- */
-static void nic_wv_rc(link_t *item)
-{
-}
-
-/**
- * Hash table helper function
- */
-static hash_index_t nic_wv_hash(unsigned long keys[])
-{
-        return keys[0] % NIC_WV_HASH_COUNT;
-}
-
-/**
  * Initializes the WOL virtues structure
  *
@@ -77 +73 @@
 int nic_wol_virtues_init(nic_wol_virtues_t *wvs)
 {
-        bzero(wvs, sizeof (nic_wol_virtues_t));
-        wvs->table_operations.compare = nic_wv_compare;
+        bzero(wvs, sizeof(nic_wol_virtues_t));
         wvs->table_operations.hash = nic_wv_hash;
-        wvs->table_operations.remove_callback = nic_wv_rc;
-        if (!hash_table_create(&wvs->table, NIC_WV_HASH_COUNT, 1,
-                &wvs->table_operations)) {
+        wvs->table_operations.key_hash = nic_wv_key_hash;
+        wvs->table_operations.match = nic_wv_match;
+        wvs->table_operations.equal = 0;
+        wvs->table_operations.remove_callback = 0;
+        
+        if (!hash_table_create(&wvs->table, 0, 1, &wvs->table_operations)) {
                 return ENOMEM;
         }
@@ -172 +170 @@
         } while (NULL !=
                 hash_table_find(&wvs->table, (unsigned long *) &virtue->id));
-        hash_table_insert(&wvs->table,
-                (unsigned long *) &virtue->id, &virtue->item);
+        hash_table_insert(&wvs->table, &virtue->item);
         virtue->next = wvs->lists[virtue->type];
         wvs->lists[virtue->type] = virtue;