Index: kernel/generic/include/adt/hash.h
===================================================================
--- kernel/generic/include/adt/hash.h	(revision 300f4c4dd43b87fb910ea1cfccdc3280c2bdd2ca)
+++ kernel/generic/include/adt/hash.h	(revision 07cb0108f9a269b86e7dd3c0635e5f78a12c9a37)
@@ -45,11 +45,11 @@
 	 * Public domain.
 	 */
-	hash = ~hash + (hash << 15); 
+	hash = ~hash + (hash << 15);
 	hash = hash ^ (hash >> 12);
 	hash = hash + (hash << 2);
 	hash = hash ^ (hash >> 4);
-	hash = hash * 2057; 
+	hash = hash * 2057;
 	hash = hash ^ (hash >> 16);
-	return hash;	
+	return hash;
 }
 
@@ -65,6 +65,6 @@
 	hash = hash ^ (hash >> 4);
 	hash = hash * 0x27d4eb2d;
-	hash = hash ^ (hash >> 15);	
-	/* 
+	hash = hash ^ (hash >> 15);
+	/*
 	 * Lower order bits are mixed more thoroughly. Swap them with
 	 * the higher order bits and make the resulting higher order bits
@@ -105,7 +105,7 @@
 	 * http://burtleburtle.net/bob/c/lookup3.c
 	 */
-	seed ^= hash + 0x9e3779b9 
+	seed ^= hash + 0x9e3779b9
 		+ ((seed << 5) | (seed >> (sizeof(size_t) * 8 - 5)));
-	return seed;	
+	return seed;
 }
 
Index: kernel/generic/include/adt/hash_table.h
===================================================================
--- kernel/generic/include/adt/hash_table.h	(revision 300f4c4dd43b87fb910ea1cfccdc3280c2bdd2ca)
+++ kernel/generic/include/adt/hash_table.h	(revision 07cb0108f9a269b86e7dd3c0635e5f78a12c9a37)
@@ -1,4 +1,6 @@
 /*
  * Copyright (c) 2006 Jakub Jermar
+ * Copyright (c) 2012 Adam Hraska
+ * 
  * All rights reserved.
  *
@@ -27,5 +29,5 @@
  */
 
-/** @addtogroup genericadt
+/** @addtogroup libc
  * @{
  */
@@ -33,54 +35,70 @@
  */
 
-#ifndef KERN_HASH_TABLE_H_
-#define KERN_HASH_TABLE_H_
+#ifndef LIBC_HASH_TABLE_H_
+#define LIBC_HASH_TABLE_H_
 
 #include <adt/list.h>
-#include <typedefs.h>
+#include <stdbool.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 {
-	/** Hash function.
-	 *
-	 * @param key 	Array of keys needed to compute hash index. All keys must
-	 * 		be passed.
-	 *
-	 * @return Index into hash table.
-	 */
-	size_t (* hash)(sysarg_t key[]);
+	/** Returns the hash of the key stored in the item (ie its lookup key). */
+	size_t (*hash)(const ht_link_t *item);
 	
-	/** Hash table item comparison 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 (*compare)(sysarg_t key[], size_t keys, link_t *item);
+	/** Returns the hash of the key. */
+	size_t (*key_hash)(void *key);
+	
+	/** True if the items are equal (have the same lookup keys). */
+	bool (*equal)(const ht_link_t *item1, const ht_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.
+	 * 
+	 * 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;
+	void (*remove_callback)(ht_link_t *item);
+} hash_table_ops_t;
 
 /** Hash table structure. */
 typedef struct {
-	list_t *entry;
-	size_t entries;
-	size_t max_keys;
-	hash_table_operations_t *op;
+	hash_table_ops_t *op;
+	list_t *bucket;
+	size_t bucket_cnt;
+	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 void hash_table_create(hash_table_t *h, size_t m, size_t max_keys,
-    hash_table_operations_t *op);
-extern void hash_table_insert(hash_table_t *h, sysarg_t key[], link_t *item);
-extern link_t *hash_table_find(hash_table_t *h, sysarg_t key[]);
-extern void hash_table_remove(hash_table_t *h, sysarg_t key[], size_t keys);
-extern void hash_table_remove_item(hash_table_t *h, link_t *item);
+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 *, 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 *);
+
 
 #endif
Index: kernel/generic/include/ddi/irq.h
===================================================================
--- kernel/generic/include/ddi/irq.h	(revision 300f4c4dd43b87fb910ea1cfccdc3280c2bdd2ca)
+++ kernel/generic/include/ddi/irq.h	(revision 07cb0108f9a269b86e7dd3c0635e5f78a12c9a37)
@@ -102,5 +102,5 @@
 typedef struct irq {
 	/** Hash table link. */
-	link_t link;
+	ht_link_t link;
 	
 	/** Lock protecting everything in this structure
Index: kernel/generic/include/lib/ra.h
===================================================================
--- kernel/generic/include/lib/ra.h	(revision 300f4c4dd43b87fb910ea1cfccdc3280c2bdd2ca)
+++ kernel/generic/include/lib/ra.h	(revision 07cb0108f9a269b86e7dd3c0635e5f78a12c9a37)
@@ -71,5 +71,13 @@
 typedef struct {
 	link_t segment_link;	/**< Span's segment list link. */
-	link_t fu_link;		/**< Span's free list or used hash link. */
+
+	/*
+	 * A segment cannot be both on the free list and in the used hash.
+	 * Their respective links can therefore occupy the same space.
+	 */
+	union {
+		link_t fl_link;		/**< Span's free list link. */
+		ht_link_t uh_link;	/**< Span's used hash link. */
+	};
 
 	uintptr_t base;		/**< Segment base. */
Index: kernel/generic/include/synch/futex.h
===================================================================
--- kernel/generic/include/synch/futex.h	(revision 300f4c4dd43b87fb910ea1cfccdc3280c2bdd2ca)
+++ kernel/generic/include/synch/futex.h	(revision 07cb0108f9a269b86e7dd3c0635e5f78a12c9a37)
@@ -38,4 +38,5 @@
 #include <typedefs.h>
 #include <synch/waitq.h>
+#include <adt/hash_table.h>
 
 /** Kernel-side futex structure. */
@@ -46,5 +47,5 @@
 	waitq_t wq;
 	/** Futex hash table link. */
-	link_t ht_link;
+	ht_link_t ht_link;
 	/** Number of tasks that reference this futex. */
 	size_t refcount;