Index: kernel/generic/src/adt/hash_table.c
===================================================================
--- kernel/generic/src/adt/hash_table.c	(revision 68f46712429fd2645b41fba94e5e2913e9ec3be0)
+++ kernel/generic/src/adt/hash_table.c	(revision 591b989e1751b3ac580286c9c1bc10a9650d1fb9)
@@ -1,4 +1,6 @@
 /*
- * Copyright (c) 2006 Jakub Jermar
+ * Copyright (c) 2008 Jakub Jermar
+ * Copyright (c) 2012 Adam Hraska
+ * 
  * All rights reserved.
  *
@@ -27,181 +29,439 @@
  */
 
-/** @addtogroup genericadt
+/** @addtogroup libc
  * @{
  */
-
-/**
- * @file
- * @brief Implementation of generic chained hash table.
- *
- * This file contains implementation of generic chained hash table.
+/** @file
+ */
+
+/*
+ * 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.
  */
 
 #include <adt/hash_table.h>
 #include <adt/list.h>
+#include <mm/slab.h>
 #include <assert.h>
-#include <typedefs.h>
-#include <mm/slab.h>
-#include <mem.h>
+#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);
+static bool alloc_table(size_t, list_t **);
+static void clear_items(hash_table_t *);
+static void resize(hash_table_t *, size_t);
+static void grow_if_needed(hash_table_t *);
+static void shrink_if_needed(hash_table_t *);
+
+/* Dummy do nothing callback to invoke in place of remove_callback == NULL. */
+static void nop_remove_callback(ht_link_t *item)
+{
+	/* no-op */
+}
+
 
 /** Create chained hash table.
  *
- * @param h Hash table structure. Will be initialized by this call.
- * @param m Number of slots in the hash table.
- * @param max_keys Maximal number of keys needed to identify an item.
- * @param op Hash table operations structure.
- */
-void hash_table_create(hash_table_t *h, size_t m, size_t max_keys, hash_table_operations_t *op)
-{
-	size_t i;
-
+ * @param h        Hash table structure. Will be initialized by this call.
+ * @param init_size Initial desired number of hash table buckets. Pass zero
+ *                 if you want the default initial size. 
+ * @param max_load The table is resized when the average load per bucket
+ *                 exceeds this number. Pass zero if you want the default.
+ * @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, size_t init_size, size_t max_load,
+    hash_table_ops_t *op)
+{
 	assert(h);
-	assert(op);
-	assert(op->hash);
-	assert(op->compare);
-	assert(max_keys > 0);
-	
-	h->entry = (list_t *) malloc(m * sizeof(list_t), 0);
-	if (!h->entry)
-		panic("Cannot allocate memory for hash table.");
-	
-	memsetb(h->entry, m * sizeof(list_t), 0);
-	
-	for (i = 0; i < m; i++)
-		list_initialize(&h->entry[i]);
-	
-	h->entries = m;
-	h->max_keys = max_keys;
+	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);
+	
+	if (!alloc_table(h->bucket_cnt, &h->bucket))
+		return false;
+	
+	h->max_load = (max_load == 0) ? HT_MAX_LOAD : max_load;
+	h->item_cnt = 0;
 	h->op = op;
-}
-
-/** Insert item into hash table.
- *
- * @param h Hash table.
- * @param key Array of all keys necessary to compute hash index.
+	h->full_item_cnt = h->max_load * h->bucket_cnt;
+	h->apply_ongoing = false;
+
+	if (h->op->remove_callback == NULL) {
+		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 = NULL;
+	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
+ *
+ * @param h Hash table to be cleared
+ */
+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_link);
+		}
+	}
+	
+	h->item_cnt = 0;
+}
+
+/** Insert item into a hash table.
+ *
+ * @param h    Hash table.
  * @param item Item to be inserted into the hash table.
  */
-void hash_table_insert(hash_table_t *h, sysarg_t key[], link_t *item)
-{
-	size_t chain;
-	
+void hash_table_insert(hash_table_t *h, ht_link_t *item)
+{
 	assert(item);
-	assert(h);
-	assert(h->op);
-	assert(h->op->hash);
-	assert(h->op->compare);
-	
-	chain = h->op->hash(key);
-	assert(chain < h->entries);
-	
-	list_append(item, &h->entry[chain]);
+	assert(h && h->bucket);
+	assert(!h->apply_ongoing);
+	
+	size_t idx = h->op->hash(item) % h->bucket_cnt;
+	
+	list_append(&item->link, &h->bucket[idx]);
+	++h->item_cnt;
+	grow_if_needed(h);
+}
+
+
+/** Insert item into a hash table if not already present.
+ *
+ * @param h    Hash table.
+ * @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, ht_link_t *item)
+{
+	assert(item);
+	assert(h && h->bucket && h->bucket_cnt);
+	assert(h->op && h->op->hash && h->op->equal);
+	assert(!h->apply_ongoing);
+	
+	size_t idx = h->op->hash(item) % h->bucket_cnt;
+	
+	/* Check for duplicates. */
+	list_foreach(h->bucket[idx], link, ht_link_t, cur_link) {
+		/* 
+		 * We could filter out items using their hashes first, but 
+		 * calling equal() might very well be just as fast.
+		 */
+		if (h->op->equal(cur_link, item))
+			return false;
+	}
+	
+	list_append(&item->link, &h->bucket[idx]);
+	++h->item_cnt;
+	grow_if_needed(h);
+	
+	return true;
 }
 
 /** Search hash table for an item matching keys.
  *
- * @param h Hash table.
+ * @param h   Hash table.
  * @param key Array of all keys needed to compute hash index.
  *
  * @return Matching item on success, NULL if there is no such item.
- */
-link_t *hash_table_find(hash_table_t *h, sysarg_t key[])
-{
-	size_t chain;
-	
-	assert(h);
-	assert(h->op);
-	assert(h->op->hash);
-	assert(h->op->compare);
-	
-	chain = h->op->hash(key);
-	assert(chain < h->entries);
-	
-	link_t *cur = list_first(&h->entry[chain]);
-	while (cur != NULL) {
-		if (h->op->compare(key, h->max_keys, cur)) {
-			/*
-			 * The entry is there.
+ *
+ */
+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], link, ht_link_t, cur_link) {
+		/* 
+		 * Is this is the item we are looking for? We could have first 
+		 * checked if the hashes match but op->key_equal() may very well be 
+		 * just as fast as op->hash().
+		 */
+		if (h->op->key_equal(key, cur_link)) {
+			return cur_link;
+		}
+	}
+	
+	return NULL;
+}
+
+/** 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;
+}
+
+/** Remove all matching items from hash table.
+ *
+ * For each removed item, h->remove_callback() is called.
+ *
+ * @param h    Hash table.
+ * @param key  Array of keys that will be compared against items of
+ *             the hash table.
+ * 
+ * @return Returns the number of removed items.
+ */
+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, ht_link_t *item)
+{
+	assert(item);
+	assert(h && h->bucket);
+	assert(link_in_use(&item->link));
+
+	list_remove(&item->link);
+	--h->item_cnt;
+	h->op->remove_callback(item);
+	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) {
+			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!).
 			 */
-			return cur;
-		}
-		cur = list_next(cur, &h->entry[chain]);
-	}
-	
-	return NULL;
-}
-
-/** Remove all matching items from hash table.
- *
- * For each removed item, h->remove_callback() is called (if not NULL).
- *
- * @param h Hash table.
- * @param key Array of keys that will be compared against items of the hash table.
- * @param keys Number of keys in the key array.
- */
-void hash_table_remove(hash_table_t *h, sysarg_t key[], size_t keys)
-{
-	size_t chain;
-	
-	assert(h);
-	assert(h->op);
-	assert(h->op->hash);
-	assert(h->op->compare);
-	assert(keys <= h->max_keys);
-	
-	
-	if (keys == h->max_keys) {
-		link_t *cur;
+			if (!f(cur_link, arg))
+				goto out;
+		}
+	}
+out:
+	h->apply_ongoing = false;
+	
+	shrink_if_needed(h);
+	grow_if_needed(h);
+}
+
+/** 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);
 		
-		/*
-		 * All keys are known, hash_table_find() can be used to find the entry.
+	list_t *buckets = malloc(bucket_cnt * sizeof(list_t), FRAME_ATOMIC);
+	if (!buckets)
+		return false;
+	
+	for (size_t i = 0; i < bucket_cnt; i++)
+		list_initialize(&buckets[i]);
+
+	*pbuckets = buckets;
+	return true;
+}
+
+
+/** 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). 
+		 * Shrink from 2n + 1 to n. Integer division discards the +1.
 		 */
-	
-		cur = hash_table_find(h, key);
-		if (cur) {
-			list_remove(cur);
-			if (h->op->remove_callback)
-				h->op->remove_callback(cur);
-		}
+		size_t new_bucket_cnt = h->bucket_cnt / 2;
+		resize(h, new_bucket_cnt);
+	}
+}
+
+/** 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 (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;
+		resize(h, new_bucket_cnt);
+	}
+}
+
+/** 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;
-	}
-	
-	/*
-	 * Fewer keys were passed.
-	 * Any partially matching entries are to be removed.
-	 */
-	for (chain = 0; chain < h->entries; chain++) {
-		link_t *cur;
-		for (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);
-				if (h->op->remove_callback)
-					h->op->remove_callback(hlp);
-				
-				continue;
+	
+	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]);
 			}
 		}
 	}
-}
-
-/** Remove an existing item from hash table.
- *
- * @param h     Hash table.
- * @param item  Item to remove from the hash table.
- */
-void hash_table_remove_item(hash_table_t *h, link_t *item)
-{
-	assert(h);
-	assert(h->op);
-	
-	list_remove(item);
-	if (h->op->remove_callback)
-		h->op->remove_callback(item);
-}
+	
+	free(h->bucket);
+	h->bucket = new_buckets;
+	h->bucket_cnt = new_bucket_cnt;
+	h->full_item_cnt = h->max_load * h->bucket_cnt;
+}
+
 
 /** @}
Index: kernel/generic/src/ddi/irq.c
===================================================================
--- kernel/generic/src/ddi/irq.c	(revision 68f46712429fd2645b41fba94e5e2913e9ec3be0)
+++ kernel/generic/src/ddi/irq.c	(revision 591b989e1751b3ac580286c9c1bc10a9650d1fb9)
@@ -40,4 +40,5 @@
 
 #include <ddi/irq.h>
+#include <adt/hash.h>
 #include <adt/hash_table.h>
 #include <mm/slab.h>
@@ -71,16 +72,15 @@
 hash_table_t irq_uspace_hash_table;
 
-static size_t irq_ht_hash(sysarg_t *key);
-static bool irq_ht_compare(sysarg_t *key, size_t keys, link_t *item);
-static void irq_ht_remove(link_t *item);
-
-static hash_table_operations_t irq_ht_ops = {
+static size_t irq_ht_hash(const ht_link_t *);
+static size_t irq_ht_key_hash(void *);
+static bool irq_ht_equal(const ht_link_t *, const ht_link_t *);
+static bool irq_ht_key_equal(void *, const ht_link_t *);
+
+static hash_table_ops_t irq_ht_ops = {
 	.hash = irq_ht_hash,
-	.compare = irq_ht_compare,
-	.remove_callback = irq_ht_remove,
+	.key_hash = irq_ht_key_hash,
+	.equal = irq_ht_equal,
+	.key_equal = irq_ht_key_equal
 };
-
-/** Number of buckets in either of the hash tables */
-static size_t buckets;
 
 /** Last valid INR */
@@ -95,5 +95,4 @@
 void irq_init(size_t inrs, size_t chains)
 {
-	buckets = chains;
 	last_inr = inrs - 1;
 
@@ -102,6 +101,6 @@
 	assert(irq_slab);
 
-	hash_table_create(&irq_uspace_hash_table, chains, 2, &irq_ht_ops);
-	hash_table_create(&irq_kernel_hash_table, chains, 2, &irq_ht_ops);
+	hash_table_create(&irq_uspace_hash_table, chains, 0, &irq_ht_ops);
+	hash_table_create(&irq_kernel_hash_table, chains, 0, &irq_ht_ops);
 }
 
@@ -114,5 +113,4 @@
 {
 	memsetb(irq, sizeof(irq_t), 0);
-	link_initialize(&irq->link);
 	irq_spinlock_initialize(&irq->lock, "irq.lock");
 	irq->inr = -1;
@@ -131,54 +129,28 @@
 void irq_register(irq_t *irq)
 {
-	sysarg_t key[] = {
-		[IRQ_HT_KEY_INR] = (sysarg_t) irq->inr,
-		[IRQ_HT_KEY_MODE] = (sysarg_t) IRQ_HT_MODE_NO_CLAIM 
-	};
-	
 	irq_spinlock_lock(&irq_kernel_hash_table_lock, true);
 	irq_spinlock_lock(&irq->lock, false);
-	hash_table_insert(&irq_kernel_hash_table, key, &irq->link);
+	hash_table_insert(&irq_kernel_hash_table, &irq->link);
 	irq_spinlock_unlock(&irq->lock, false);
 	irq_spinlock_unlock(&irq_kernel_hash_table_lock, true);
 }
 
-/** Search and lock the uspace IRQ hash table */
-static irq_t *irq_dispatch_and_lock_uspace(inr_t inr)
-{
-	link_t *lnk;
-	sysarg_t key[] = {
-		[IRQ_HT_KEY_INR] = (sysarg_t) inr,
-		[IRQ_HT_KEY_MODE] = (sysarg_t) IRQ_HT_MODE_CLAIM
-	};
-	
-	irq_spinlock_lock(&irq_uspace_hash_table_lock, false);
-	lnk = hash_table_find(&irq_uspace_hash_table, key);
-	if (lnk) {
-		irq_t *irq = hash_table_get_instance(lnk, irq_t, link);
-		irq_spinlock_unlock(&irq_uspace_hash_table_lock, false);
-		return irq;
+/** Search and lock an IRQ hash table */
+static irq_t *
+irq_dispatch_and_lock_table(hash_table_t *h, irq_spinlock_t *l, inr_t inr)
+{
+	irq_spinlock_lock(l, false);
+	for (ht_link_t *lnk = hash_table_find(h, &inr); lnk;
+	    lnk = hash_table_find_next(h, lnk)) {
+		irq_t *irq = hash_table_get_inst(lnk, irq_t, link);
+		irq_spinlock_lock(&irq->lock, false);
+		if (irq->claim(irq) == IRQ_ACCEPT) {
+			/* leave irq locked */
+			irq_spinlock_unlock(l, false);
+			return irq;
+		}
+		irq_spinlock_unlock(&irq->lock, false);
 	}
-	irq_spinlock_unlock(&irq_uspace_hash_table_lock, false);
-	
-	return NULL;
-}
-
-/** Search and lock the kernel IRQ hash table */
-static irq_t *irq_dispatch_and_lock_kernel(inr_t inr)
-{
-	link_t *lnk;
-	sysarg_t key[] = {
-		[IRQ_HT_KEY_INR] = (sysarg_t) inr,
-		[IRQ_HT_KEY_MODE] = (sysarg_t) IRQ_HT_MODE_CLAIM
-	};
-	
-	irq_spinlock_lock(&irq_kernel_hash_table_lock, false);
-	lnk = hash_table_find(&irq_kernel_hash_table, key);
-	if (lnk) {
-		irq_t *irq = hash_table_get_instance(lnk, irq_t, link);
-		irq_spinlock_unlock(&irq_kernel_hash_table_lock, false);
-		return irq;
-	}
-	irq_spinlock_unlock(&irq_kernel_hash_table_lock, false);
+	irq_spinlock_unlock(l, false);
 	
 	return NULL;
@@ -209,80 +181,50 @@
 	
 	if (console_override) {
-		irq_t *irq = irq_dispatch_and_lock_kernel(inr);
+		irq_t *irq = irq_dispatch_and_lock_table(&irq_kernel_hash_table,
+		    &irq_kernel_hash_table_lock, inr);
 		if (irq)
 			return irq;
 		
-		return irq_dispatch_and_lock_uspace(inr);
+		return irq_dispatch_and_lock_table(&irq_uspace_hash_table,
+		    &irq_uspace_hash_table_lock, inr);
 	}
 	
-	irq_t *irq = irq_dispatch_and_lock_uspace(inr);
+	irq_t *irq = irq_dispatch_and_lock_table(&irq_uspace_hash_table,
+	    &irq_uspace_hash_table_lock, inr);
 	if (irq)
 		return irq;
 	
-	return irq_dispatch_and_lock_kernel(inr);
-}
-
-/** Compute hash index for the key
- *
- * @param key  The first of the keys is inr and the second is mode. Only inr is
- *             used to compute the hash.
- *
- * @return Index into the hash table.
- *
- */
-size_t irq_ht_hash(sysarg_t key[])
-{
-	inr_t inr = (inr_t) key[IRQ_HT_KEY_INR];
-	return inr % buckets;
-}
-
-/** Compare hash table element with a key
- *
- * If mode is IRQ_HT_MODE_CLAIM, the result of the claim() function is used for
- * the match. Otherwise the key does not match.
- *
- * This function assumes interrupts are already disabled.
- *
- * @param key   Keys (i.e. inr and mode).
- * @param keys  This is 2. 
- * @param item  The item to compare the key with.
- *
- * @return True on match
- * @return False on no match
- *
- */
-bool irq_ht_compare(sysarg_t key[], size_t keys, link_t *item)
-{
-	irq_t *irq = hash_table_get_instance(item, irq_t, link);
-	inr_t inr = (inr_t) key[IRQ_HT_KEY_INR];
-	irq_ht_mode_t mode = (irq_ht_mode_t) key[IRQ_HT_KEY_MODE];
-	
-	bool rv;
-	
-	irq_spinlock_lock(&irq->lock, false);
-	if (mode == IRQ_HT_MODE_CLAIM) {
-		/* Invoked by irq_dispatch_and_lock(). */
-		rv = ((irq->inr == inr) && (irq->claim(irq) == IRQ_ACCEPT));
-	} else {
-		/* Invoked by irq_find_and_lock(). */
-		rv = false;
-	}
-	
-	/* unlock only on non-match */
-	if (!rv)
-		irq_spinlock_unlock(&irq->lock, false);
-	
-	return rv;
-}
-
-/** Unlock IRQ structure after hash_table_remove()
- *
- * @param lnk  Link in the removed and locked IRQ structure.
- */
-void irq_ht_remove(link_t *lnk)
-{
-	irq_t *irq __attribute__((unused))
-	    = hash_table_get_instance(lnk, irq_t, link);
-	irq_spinlock_unlock(&irq->lock, false);
+	return irq_dispatch_and_lock_table(&irq_kernel_hash_table,
+	    &irq_kernel_hash_table_lock, inr);
+}
+
+/** Return the hash of the key stored in the item. */
+size_t irq_ht_hash(const ht_link_t *item)
+{
+	irq_t *irq = hash_table_get_inst(item, irq_t, link);
+	return hash_mix(irq->inr);
+}
+
+/** Return the hash of the key. */
+size_t irq_ht_key_hash(void *key)
+{
+	inr_t *inr = (inr_t *) key;
+	return hash_mix(*inr);
+}
+
+/** Return true if the items have the same lookup key. */
+bool irq_ht_equal(const ht_link_t *item1, const ht_link_t *item2)
+{
+	irq_t *irq1 = hash_table_get_inst(item1, irq_t, link);
+	irq_t *irq2 = hash_table_get_inst(item2, irq_t, link);
+	return irq1->inr == irq2->inr;
+}
+
+/** Return true if the key is equal to the item's lookup key. */
+bool irq_ht_key_equal(void *key, const ht_link_t *item)
+{
+	inr_t *inr = (inr_t *) key;
+	irq_t *irq = hash_table_get_inst(item, irq_t, link);
+	return irq->inr == *inr;
 }
 
Index: kernel/generic/src/ipc/irq.c
===================================================================
--- kernel/generic/src/ipc/irq.c	(revision 68f46712429fd2645b41fba94e5e2913e9ec3be0)
+++ kernel/generic/src/ipc/irq.c	(revision 591b989e1751b3ac580286c9c1bc10a9650d1fb9)
@@ -298,9 +298,4 @@
     irq_code_t *ucode)
 {
-	sysarg_t key[] = {
-		[IRQ_HT_KEY_INR] = (sysarg_t) inr,
-		[IRQ_HT_KEY_MODE] = (sysarg_t) IRQ_HT_MODE_NO_CLAIM
-	};
-	
 	if ((inr < 0) || (inr > last_inr))
 		return ELIMIT;
@@ -351,5 +346,5 @@
 	
 	irq->notif_cfg.hashed_in = true;
-	hash_table_insert(&irq_uspace_hash_table, key, &irq->link);
+	hash_table_insert(&irq_uspace_hash_table, &irq->link);
 	
 	irq_spinlock_unlock(&irq->lock, false);
@@ -388,5 +383,5 @@
 	}
 
-	/* kobj->irq->lock unlocked by the hash table remove_callback */
+	irq_spinlock_unlock(&kobj->irq->lock, false);
 	irq_spinlock_unlock(&irq_uspace_hash_table_lock, true);
 
Index: kernel/generic/src/lib/ra.c
===================================================================
--- kernel/generic/src/lib/ra.c	(revision 68f46712429fd2645b41fba94e5e2913e9ec3be0)
+++ kernel/generic/src/lib/ra.c	(revision 591b989e1751b3ac580286c9c1bc10a9650d1fb9)
@@ -50,4 +50,5 @@
 #include <panic.h>
 #include <adt/list.h>
+#include <adt/hash.h>
 #include <adt/hash_table.h>
 #include <align.h>
@@ -57,23 +58,30 @@
 static slab_cache_t *ra_segment_cache;
 
-#define USED_BUCKETS	1024
-
-static size_t used_hash(sysarg_t *key)
-{
-	return ((*key >> 2) & (USED_BUCKETS - 1));
-}
-
-static bool used_compare(sysarg_t *key, size_t keys, link_t *item)
-{
-	ra_segment_t *seg;
-
-	seg = hash_table_get_instance(item, ra_segment_t, fu_link);
-	return seg->base == *key;
-}
-
-static hash_table_operations_t used_ops = {
+/** Return the hash of the key stored in the item */
+static size_t used_hash(const ht_link_t *item)
+{
+	ra_segment_t *seg = hash_table_get_inst(item, ra_segment_t, uh_link);
+	return hash_mix(seg->base);
+}
+
+/** Return the hash of the key */
+static size_t used_key_hash(void *key)
+{
+	uintptr_t *base = (uintptr_t *) key;
+	return hash_mix(*base);
+}
+
+/** Return true if the key is equal to the item's lookup key */
+static bool used_key_equal(void *key, const ht_link_t *item)
+{
+	uintptr_t *base = (sysarg_t *) key;
+	ra_segment_t *seg = hash_table_get_inst(item, ra_segment_t, uh_link);
+	return seg->base == *base;
+}
+
+static hash_table_ops_t used_ops = {
 	.hash = used_hash,
-	.compare = used_compare,
-	.remove_callback = NULL,
+	.key_hash = used_key_hash,
+	.key_equal = used_key_equal
 };
 
@@ -97,5 +105,5 @@
 
 	link_initialize(&seg->segment_link);
-	link_initialize(&seg->fu_link);
+	link_initialize(&seg->fl_link);
 
 	seg->base = base;
@@ -160,5 +168,5 @@
 	list_initialize(&span->segments);
 
-	hash_table_create(&span->used, USED_BUCKETS, 1, &used_ops);
+	hash_table_create(&span->used, 0, 0, &used_ops);
 
 	for (i = 0; i <= span->max_order; i++)
@@ -171,5 +179,5 @@
 
 	/* Insert the first segment into the respective free list. */
-	list_append(&seg->fu_link, &span->free[span->max_order]);
+	list_append(&seg->fl_link, &span->free[span->max_order]);
 
 	return span;
@@ -232,5 +240,5 @@
 		/* Take the first segment from the free list. */
 		seg = list_get_instance(list_first(&span->free[order]),
-		    ra_segment_t, fu_link);
+		    ra_segment_t, fl_link);
 
 		assert(seg->flags & RA_SEGMENT_FREE);
@@ -274,5 +282,5 @@
 			    &seg->segment_link);
 			pred_order = fnzb(ra_segment_size_get(pred));
-			list_append(&pred->fu_link, &span->free[pred_order]);
+			list_append(&pred->fl_link, &span->free[pred_order]);
 		}
 		if (succ) {
@@ -282,15 +290,14 @@
 			    &seg->segment_link);
 			succ_order = fnzb(ra_segment_size_get(succ));
-			list_append(&succ->fu_link, &span->free[succ_order]);
+			list_append(&succ->fl_link, &span->free[succ_order]);
 		}
 
 		/* Now remove the found segment from the free list. */
-		list_remove(&seg->fu_link);
+		list_remove(&seg->fl_link);
 		seg->base = newbase;
 		seg->flags &= ~RA_SEGMENT_FREE;
 
 		/* Hash-in the segment into the used hash. */
-		sysarg_t key = seg->base;
-		hash_table_insert(&span->used, &key, &seg->fu_link);
+		hash_table_insert(&span->used, &seg->uh_link);
 
 		*base = newbase;
@@ -304,5 +311,5 @@
 {
 	sysarg_t key = base;
-	link_t *link;
+	ht_link_t *link;
 	ra_segment_t *seg;
 	ra_segment_t *pred;
@@ -318,10 +325,10 @@
 		    PRIxn ", size=%" PRIdn ").", base, size);
 	}
-	seg = hash_table_get_instance(link, ra_segment_t, fu_link);
+	seg = hash_table_get_inst(link, ra_segment_t, uh_link);
 
 	/*
 	 * Hash out the segment.
 	 */
-	hash_table_remove(&span->used, &key, 1);
+	hash_table_remove_item(&span->used, link);
 
 	assert(!(seg->flags & RA_SEGMENT_FREE));
@@ -333,5 +340,5 @@
 	 */
 	if (list_first(&span->segments) != &seg->segment_link) {
-		pred = hash_table_get_instance(seg->segment_link.prev,
+		pred = hash_table_get_inst(seg->segment_link.prev,
 		    ra_segment_t, segment_link);
 
@@ -345,5 +352,5 @@
 			 * away.
 			 */
-			list_remove(&pred->fu_link);
+			list_remove(&pred->fl_link);
 			list_remove(&pred->segment_link);
 			seg->base = pred->base;
@@ -355,5 +362,5 @@
 	 * Check whether the segment can be coalesced with its right neighbor.
 	 */
-	succ = hash_table_get_instance(seg->segment_link.next, ra_segment_t,
+	succ = hash_table_get_inst(seg->segment_link.next, ra_segment_t,
 	    segment_link);
 	assert(succ->base > seg->base);
@@ -364,5 +371,5 @@
 		 * and throw it away.
 		 */
-		list_remove(&succ->fu_link);
+		list_remove(&succ->fl_link);
 		list_remove(&succ->segment_link);
 		ra_segment_destroy(succ);
@@ -372,5 +379,5 @@
 	seg->flags |= RA_SEGMENT_FREE;
 	order = fnzb(ra_segment_size_get(seg));
-	list_append(&seg->fu_link, &span->free[order]);
+	list_append(&seg->fl_link, &span->free[order]);
 }
 
Index: kernel/generic/src/synch/futex.c
===================================================================
--- kernel/generic/src/synch/futex.c	(revision 68f46712429fd2645b41fba94e5e2913e9ec3be0)
+++ kernel/generic/src/synch/futex.c	(revision 591b989e1751b3ac580286c9c1bc10a9650d1fb9)
@@ -74,4 +74,5 @@
 #include <genarch/mm/page_ht.h>
 #include <adt/cht.h>
+#include <adt/hash.h>
 #include <adt/hash_table.h>
 #include <adt/list.h>
@@ -80,6 +81,4 @@
 #include <panic.h>
 #include <errno.h>
-
-#define FUTEX_HT_SIZE	1024	/* keep it a power of 2 */
 
 /** Task specific pointer to a global kernel futex object. */
@@ -108,7 +107,8 @@
 static bool find_futex_paddr(uintptr_t uaddr, uintptr_t *phys_addr);
 
-static size_t futex_ht_hash(sysarg_t *key);
-static bool futex_ht_compare(sysarg_t *key, size_t keys, link_t *item);
-static void futex_ht_remove_callback(link_t *item);
+static size_t futex_ht_hash(const ht_link_t *item);
+static size_t futex_ht_key_hash(void *key);
+static bool futex_ht_key_equal(void *key, const ht_link_t *item);
+static void futex_ht_remove_callback(ht_link_t *item);
 
 static size_t task_fut_ht_hash(const cht_link_t *link);
@@ -131,7 +131,8 @@
 
 /** Global kernel futex hash table operations. */
-static hash_table_operations_t futex_ht_ops = {
+static hash_table_ops_t futex_ht_ops = {
 	.hash = futex_ht_hash,
-	.compare = futex_ht_compare,
+	.key_hash = futex_ht_key_hash,
+	.key_equal = futex_ht_key_equal,
 	.remove_callback = futex_ht_remove_callback
 };
@@ -149,5 +150,5 @@
 void futex_init(void)
 {
-	hash_table_create(&futex_ht, FUTEX_HT_SIZE, 1, &futex_ht_ops);
+	hash_table_create(&futex_ht, 0, 0, &futex_ht_ops);
 }
 
@@ -234,5 +235,4 @@
 {
 	waitq_initialize(&futex->wq);
-	link_initialize(&futex->ht_link);
 	futex->paddr = paddr;
 	futex->refcount = 1;
@@ -256,5 +256,5 @@
 	
 	if (0 == futex->refcount) {
-		hash_table_remove(&futex_ht, &futex->paddr, 1);
+		hash_table_remove(&futex_ht, &futex->paddr);
 	}
 }
@@ -347,5 +347,5 @@
 	spinlock_lock(&futex_ht_lock);
 	
-	link_t *fut_link = hash_table_find(&futex_ht, &phys_addr);
+	ht_link_t *fut_link = hash_table_find(&futex_ht, &phys_addr);
 	
 	if (fut_link) {
@@ -355,5 +355,5 @@
 	} else {
 		futex_initialize(futex, phys_addr);
-		hash_table_insert(&futex_ht, &phys_addr, &futex->ht_link);
+		hash_table_insert(&futex_ht, &futex->ht_link);
 	}
 	
@@ -437,42 +437,35 @@
 
 
-/** Compute hash index into futex hash table.
- *
- * @param key		Address where the key (i.e. physical address of futex
- *			counter) is stored.
- *
- * @return		Index into futex hash table.
- */
-size_t futex_ht_hash(sysarg_t *key)
-{
-	return (*key & (FUTEX_HT_SIZE - 1));
-}
-
-/** Compare futex hash table item with a key.
- *
- * @param key		Address where the key (i.e. physical address of futex
- *			counter) is stored.
- *
- * @return		True if the item matches the key. False otherwise.
- */
-bool futex_ht_compare(sysarg_t *key, size_t keys, link_t *item)
+/** Return the hash of the key stored in the item */
+size_t futex_ht_hash(const ht_link_t *item)
+{
+	futex_t *futex = hash_table_get_inst(item, futex_t, ht_link);
+	return hash_mix(futex->paddr);
+}
+
+/** Return the hash of the key */
+size_t futex_ht_key_hash(void *key)
+{
+	uintptr_t *paddr = (uintptr_t *) key;
+	return hash_mix(*paddr);
+}
+
+/** Return true if the key is equal to the item's lookup key. */
+bool futex_ht_key_equal(void *key, const ht_link_t *item)
+{
+	uintptr_t *paddr = (uintptr_t *) key;
+	futex_t *futex = hash_table_get_inst(item, futex_t, ht_link);
+	return *paddr == futex->paddr;
+}
+
+/** Callback for removal items from futex hash table.
+ *
+ * @param item		Item removed from the hash table.
+ */
+void futex_ht_remove_callback(ht_link_t *item)
 {
 	futex_t *futex;
 
-	assert(keys == 1);
-
-	futex = hash_table_get_instance(item, futex_t, ht_link);
-	return *key == futex->paddr;
-}
-
-/** Callback for removal items from futex hash table.
- *
- * @param item		Item removed from the hash table.
- */
-void futex_ht_remove_callback(link_t *item)
-{
-	futex_t *futex;
-
-	futex = hash_table_get_instance(item, futex_t, ht_link);
+	futex = hash_table_get_inst(item, futex_t, ht_link);
 	free(futex);
 }