Index: uspace/app/mkexfat/mkexfat.c
===================================================================
--- uspace/app/mkexfat/mkexfat.c	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/app/mkexfat/mkexfat.c	(revision 062d9000625057300f609429080872d6492b542e)
@@ -49,4 +49,5 @@
 #include <str.h>
 #include <getopt.h>
+#include <macros.h>
 #include "exfat.h"
 #include "upcase.h"
@@ -87,5 +88,4 @@
 #define FIRST_FREE_CLUSTER   2
 
-#define min(x, y) ((x) < (y) ? (x) : (y))
 
 typedef struct exfat_cfg {
Index: uspace/app/trace/ipcp.c
===================================================================
--- uspace/app/trace/ipcp.c	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/app/trace/ipcp.c	(revision 062d9000625057300f609429080872d6492b542e)
@@ -38,4 +38,5 @@
 #include <sys/typefmt.h>
 #include <abi/ipc/methods.h>
+#include <macros.h>
 #include "ipc_desc.h"
 #include "proto.h"
@@ -52,5 +53,5 @@
 	ipc_callid_t call_hash;
 
-	link_t link;
+	ht_link_t link;
 } pending_call_t;
 
@@ -64,6 +65,5 @@
 int have_conn[MAX_PHONE];
 
-#define PCALL_TABLE_CHAINS 32
-hash_table_t pending_calls;
+static hash_table_t pending_calls;
 
 /*
@@ -73,38 +73,32 @@
 proto_t	*proto_unknown;		/**< Protocol with no known methods. */
 
-static hash_index_t pending_call_hash(unsigned long key[]);
-static int pending_call_compare(unsigned long key[], hash_count_t keys,
-    link_t *item);
-static void pending_call_remove_callback(link_t *item);
-
-hash_table_operations_t pending_call_ops = {
+
+static size_t pending_call_key_hash(void *key)
+{
+	ipc_callid_t *call_id = (ipc_callid_t *)key;
+	return *call_id;
+}
+
+static size_t pending_call_hash(const ht_link_t *item)
+{
+	pending_call_t *hs = hash_table_get_inst(item, pending_call_t, link);
+	return hs->call_hash;
+}
+
+static bool pending_call_key_equal(void *key, const ht_link_t *item)
+{
+	ipc_callid_t *call_id = (ipc_callid_t *)key;
+	pending_call_t *hs = hash_table_get_inst(item, pending_call_t, link);
+
+	return *call_id == hs->call_hash;
+}
+
+static hash_table_ops_t pending_call_ops = {
 	.hash = pending_call_hash,
-	.compare = pending_call_compare,
-	.remove_callback = pending_call_remove_callback
+	.key_hash = pending_call_key_hash,
+	.key_equal = pending_call_key_equal,
+	.equal = 0,
+	.remove_callback = 0
 };
-
-
-static hash_index_t pending_call_hash(unsigned long key[])
-{
-//	printf("pending_call_hash\n");
-	return key[0] % PCALL_TABLE_CHAINS;
-}
-
-static int pending_call_compare(unsigned long key[], hash_count_t keys,
-    link_t *item)
-{
-	pending_call_t *hs;
-
-//	printf("pending_call_compare\n");
-	hs = hash_table_get_instance(item, pending_call_t, link);
-
-	// FIXME: this will fail if sizeof(long) < sizeof(void *).
-	return key[0] == hs->call_hash;
-}
-
-static void pending_call_remove_callback(link_t *item)
-{
-//	printf("pending_call_remove_callback\n");
-}
 
 
@@ -177,5 +171,6 @@
 	}
 
-	hash_table_create(&pending_calls, PCALL_TABLE_CHAINS, 1, &pending_call_ops);
+	bool ok = hash_table_create(&pending_calls, 0, 0, &pending_call_ops);
+	assert(ok);
 }
 
@@ -190,5 +185,4 @@
 	pending_call_t *pcall;
 	proto_t *proto;
-	unsigned long key[1];
 	oper_t *oper;
 	sysarg_t *args;
@@ -254,7 +248,5 @@
 	pcall->oper = oper;
 
-	key[0] = hash;
-
-	hash_table_insert(&pending_calls, key, &pcall->link);
+	hash_table_insert(&pending_calls, &pcall->link);
 }
 
@@ -334,7 +326,6 @@
 void ipcp_call_in(ipc_call_t *call, ipc_callid_t hash)
 {
-	link_t *item;
+	ht_link_t *item;
 	pending_call_t *pcall;
-	unsigned long key[1];
 	
 	if ((hash & IPC_CALLID_ANSWERED) == 0 && hash != IPCP_CALLID_SYNC) {
@@ -347,7 +338,6 @@
 	
 	hash = hash & ~IPC_CALLID_ANSWERED;
-	key[0] = hash;
-	
-	item = hash_table_find(&pending_calls, key);
+	
+	item = hash_table_find(&pending_calls, &hash);
 	if (item == NULL)
 		return; /* No matching question found */
@@ -357,6 +347,6 @@
 	 */
 	
-	pcall = hash_table_get_instance(item, pending_call_t, link);
-	hash_table_remove(&pending_calls, key, 1);
+	pcall = hash_table_get_inst(item, pending_call_t, link);
+	hash_table_remove(&pending_calls, &hash);
 	
 	parse_answer(hash, pcall, call);
Index: uspace/app/trace/proto.c
===================================================================
--- uspace/app/trace/proto.c	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/app/trace/proto.c	(revision 062d9000625057300f609429080872d6492b542e)
@@ -40,117 +40,103 @@
 #include "proto.h"
 
-#define SRV_PROTO_TABLE_CHAINS 32
-#define METHOD_OPER_TABLE_CHAINS 32
-
-hash_table_t srv_proto;
+
+/* Maps service number to protocol */
+static hash_table_t srv_proto;
 
 typedef struct {
-	unsigned srv;
+	int srv;
 	proto_t *proto;
-	link_t link;
+	ht_link_t link;
 } srv_proto_t;
 
 typedef struct {
-	sysarg_t method;
+	int method;
 	oper_t *oper;
-	link_t link;
+	ht_link_t link;
 } method_oper_t;
 
-static hash_index_t srv_proto_hash(unsigned long key[]);
-static int srv_proto_compare(unsigned long key[], hash_count_t keys,
-    link_t *item);
-static void srv_proto_remove_callback(link_t *item);
-
-hash_table_operations_t srv_proto_ops = {
+/* Hash table operations. */
+
+static size_t srv_proto_key_hash(void *key)
+{
+	return *(int *)key;
+}
+
+static size_t srv_proto_hash(const ht_link_t *item)
+{
+	srv_proto_t *sp = hash_table_get_inst(item, srv_proto_t, link);
+	return sp->srv;
+}
+
+static bool srv_proto_key_equal(void *key, const ht_link_t *item)
+{
+	srv_proto_t *sp = hash_table_get_inst(item, srv_proto_t, link);
+	return sp->srv == *(int *)key;
+}
+
+static hash_table_ops_t srv_proto_ops = {
 	.hash = srv_proto_hash,
-	.compare = srv_proto_compare,
-	.remove_callback = srv_proto_remove_callback
+	.key_hash = srv_proto_key_hash,
+	.key_equal = srv_proto_key_equal,
+	.equal = 0,
+	.remove_callback = 0
 };
 
-static hash_index_t method_oper_hash(unsigned long key[]);
-static int method_oper_compare(unsigned long key[], hash_count_t keys,
-    link_t *item);
-static void method_oper_remove_callback(link_t *item);
-
-hash_table_operations_t method_oper_ops = {
+
+static size_t method_oper_key_hash(void *key)
+{
+	return *(int *)key;
+}
+
+static size_t method_oper_hash(const ht_link_t *item)
+{
+	method_oper_t *mo = hash_table_get_inst(item, method_oper_t, link);
+	return mo->method;
+}
+
+static bool method_oper_key_equal(void *key, const ht_link_t *item)
+{
+	method_oper_t *mo = hash_table_get_inst(item, method_oper_t, link);
+	return mo->method == *(int *)key;
+}
+
+static hash_table_ops_t method_oper_ops = {
 	.hash = method_oper_hash,
-	.compare = method_oper_compare,
-	.remove_callback = method_oper_remove_callback
+	.key_hash = method_oper_key_hash,
+	.key_equal = method_oper_key_equal,
+	.equal = 0,
+	.remove_callback = 0
 };
 
-static hash_index_t srv_proto_hash(unsigned long key[])
-{
-	return key[0] % SRV_PROTO_TABLE_CHAINS;
-}
-
-static int srv_proto_compare(unsigned long key[], hash_count_t keys,
-    link_t *item)
+
+void proto_init(void)
+{
+	/* todo: check return value. */
+	bool ok = hash_table_create(&srv_proto, 0, 0, &srv_proto_ops);
+	assert(ok);
+}
+
+void proto_cleanup(void)
+{
+	hash_table_destroy(&srv_proto);
+}
+
+void proto_register(int srv, proto_t *proto)
 {
 	srv_proto_t *sp;
-
-	sp = hash_table_get_instance(item, srv_proto_t, link);
-
-	return key[0] == sp->srv;
-}
-
-static void srv_proto_remove_callback(link_t *item)
-{
-}
-
-static hash_index_t method_oper_hash(unsigned long key[])
-{
-	return key[0] % METHOD_OPER_TABLE_CHAINS;
-}
-
-static int method_oper_compare(unsigned long key[], hash_count_t keys,
-    link_t *item)
-{
-	method_oper_t *mo;
-
-	mo = hash_table_get_instance(item, method_oper_t, link);
-
-	return key[0] == mo->method;
-}
-
-static void method_oper_remove_callback(link_t *item)
-{
-}
-
-
-void proto_init(void)
-{
-	hash_table_create(&srv_proto, SRV_PROTO_TABLE_CHAINS, 1,
-	    &srv_proto_ops);
-}
-
-void proto_cleanup(void)
-{
-	hash_table_destroy(&srv_proto);
-}
-
-void proto_register(int srv, proto_t *proto)
-{
-	srv_proto_t *sp;
-	unsigned long key;
 
 	sp = malloc(sizeof(srv_proto_t));
 	sp->srv = srv;
 	sp->proto = proto;
-	key = srv;
-
-	hash_table_insert(&srv_proto, &key, &sp->link);
+
+	hash_table_insert(&srv_proto, &sp->link);
 }
 
 proto_t *proto_get_by_srv(int srv)
 {
-	unsigned long key;
-	link_t *item;
-	srv_proto_t *sp;
-
-	key = srv;
-	item = hash_table_find(&srv_proto, &key);
+	ht_link_t *item = hash_table_find(&srv_proto, &srv);
 	if (item == NULL) return NULL;
 
-	sp = hash_table_get_instance(item, srv_proto_t, link);
+	srv_proto_t *sp = hash_table_get_inst(item, srv_proto_t, link);
 	return sp->proto;
 }
@@ -159,6 +145,7 @@
 {
 	proto->name = name;
-	hash_table_create(&proto->method_oper, SRV_PROTO_TABLE_CHAINS, 1,
-	    &method_oper_ops);
+	/* todo: check return value. */
+	bool ok = hash_table_create(&proto->method_oper, 0, 0, &method_oper_ops);
+	assert(ok);
 }
 
@@ -181,25 +168,18 @@
 {
 	method_oper_t *mo;
-	unsigned long key;
 
 	mo = malloc(sizeof(method_oper_t));
 	mo->method = method;
 	mo->oper = oper;
-	key = method;
-
-	hash_table_insert(&proto->method_oper, &key, &mo->link);	
+
+	hash_table_insert(&proto->method_oper, &mo->link);	
 }
 
 oper_t *proto_get_oper(proto_t *proto, int method)
 {
-	unsigned long key;
-	link_t *item;
-	method_oper_t *mo;
-
-	key = method;
-	item = hash_table_find(&proto->method_oper, &key);
+	ht_link_t *item = hash_table_find(&proto->method_oper, &method);
 	if (item == NULL) return NULL;
 
-	mo = hash_table_get_instance(item, method_oper_t, link);
+	method_oper_t *mo = hash_table_get_inst(item, method_oper_t, link);
 	return mo->oper;
 }
Index: uspace/app/trace/proto.h
===================================================================
--- uspace/app/trace/proto.h	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/app/trace/proto.h	(revision 062d9000625057300f609429080872d6492b542e)
@@ -62,6 +62,4 @@
 } proto_t;
 
-/* Maps service number to protocol */
-extern hash_table_t srv_proto;
 
 extern void proto_init(void);
Index: uspace/lib/block/block.c
===================================================================
--- uspace/lib/block/block.c	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/lib/block/block.c	(revision 062d9000625057300f609429080872d6492b542e)
@@ -62,6 +62,4 @@
 static LIST_INITIALIZE(dcl);
 
-#define CACHE_BUCKETS_LOG2  10
-#define CACHE_BUCKETS       (1 << CACHE_BUCKETS_LOG2)
 
 typedef struct {
@@ -233,23 +231,30 @@
 }
 
-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)
-{
-	block_t *b = hash_table_get_instance(item, block_t, hash_link);
-	return b->lba == MERGE_LOUP32(key[0], key[1]);
-}
-
-static void cache_remove_callback(link_t *item)
-{
-}
-
-static hash_table_operations_t cache_ops = {
+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;
+}
+
+
+static hash_table_ops_t cache_ops = {
 	.hash = cache_hash,
-	.compare = cache_compare,
-	.remove_callback = cache_remove_callback
+	.key_hash = cache_key_hash,
+	.key_equal = cache_key_equal,
+	.equal = 0,
+	.remove_callback = 0
 };
 
@@ -282,6 +287,5 @@
 	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, 0, &cache_ops)) {
 		free(cache);
 		return ENOMEM;
@@ -321,9 +325,5 @@
 		}
 
-		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);
@@ -357,5 +357,4 @@
 	fibril_rwlock_initialize(&b->contents_lock);
 	link_initialize(&b->free_link);
-	link_initialize(&b->hash_link);
 }
 
@@ -377,9 +376,5 @@
 	cache_t *cache;
 	block_t *b;
-	link_t *l;
-	unsigned long key[2] = {
-		LOWER32(ba),
-		UPPER32(ba)
-	};
+	link_t *link;
 
 	int rc;
@@ -397,11 +392,11 @@
 
 	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)
@@ -441,6 +436,6 @@
 				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);
@@ -479,6 +474,6 @@
 					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
@@ -502,9 +497,5 @@
 			 */
 			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);
 		}
 
@@ -514,5 +505,5 @@
 		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);
 
 		/*
@@ -622,9 +613,5 @@
 			 * 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);
Index: uspace/lib/block/block.h
===================================================================
--- uspace/lib/block/block.h	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/lib/block/block.h	(revision 062d9000625057300f609429080872d6492b542e)
@@ -84,5 +84,5 @@
 	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;
Index: uspace/lib/c/Makefile
===================================================================
--- uspace/lib/c/Makefile	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/lib/c/Makefile	(revision 062d9000625057300f609429080872d6492b542e)
@@ -124,5 +124,4 @@
 	generic/adt/list.c \
 	generic/adt/hash_table.c \
-	generic/adt/hash_set.c \
 	generic/adt/dynamic_fifo.c \
 	generic/adt/char_map.c \
Index: pace/lib/c/generic/adt/hash_set.c
===================================================================
--- uspace/lib/c/generic/adt/hash_set.c	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ 	(revision )
@@ -1,382 +1,0 @@
-/*
- * Copyright (c) 2008 Jakub Jermar
- * Copyright (c) 2011 Radim Vansa
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- *
- * - Redistributions of source code must retain the above copyright
- *   notice, this list of conditions and the following disclaimer.
- * - Redistributions in binary form must reproduce the above copyright
- *   notice, this list of conditions and the following disclaimer in the
- *   documentation and/or other materials provided with the distribution.
- * - The name of the author may not be used to endorse or promote products
- *   derived from this software without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
- * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
- * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
- * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
- * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
- * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
- * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
- * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
- * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- */
-
-/** @addtogroup libc
- * @{
- */
-/** @file
- */
-
-#include <adt/hash_set.h>
-#include <adt/list.h>
-#include <unistd.h>
-#include <malloc.h>
-#include <assert.h>
-#include <str.h>
-
-/** Create chained hash set
- *
- * @param     h         Hash set structure to be initialized.
- * @param[in] hash      Hash function
- * @param[in] equals    Equals function
- * @param[in] init_size Initial hash set size
- *
- * @return True on success
- *
- */
-int hash_set_init(hash_set_t *h, hash_set_hash hash, hash_set_equals equals,
-    size_t init_size)
-{
-	assert(h);
-	assert(hash);
-	assert(equals);
-	
-	if (init_size < HASH_SET_MIN_SIZE)
-		init_size = HASH_SET_MIN_SIZE;
-	
-	h->table = malloc(init_size * sizeof(link_t));
-	if (!h->table)
-		return false;
-	
-	for (size_t i = 0; i < init_size; i++)
-		list_initialize(&h->table[i]);
-	
-	h->size = init_size;
-	h->count = 0;
-	h->hash = hash;
-	h->equals = equals;
-	
-	return true;
-}
-
-/** Destroy a hash table instance.
- *
- * @param h Hash table to be destroyed.
- *
- */
-void hash_set_destroy(hash_set_t *h)
-{
-	assert(h);
-	free(h->table);
-}
-
-/** Rehash the internal table to new table
- *
- * @param h         Original hash set
- * @param new_table Memory for the new table
- * @param new_size  Size of the new table
- */
-static void hash_set_rehash(hash_set_t *h, list_t *new_table,
-    size_t new_size)
-{
-	assert(new_size >= HASH_SET_MIN_SIZE);
-	
-	for (size_t bucket = 0; bucket < new_size; bucket++)
-		list_initialize(&new_table[bucket]);
-	
-	for (size_t bucket = 0; bucket < h->size; bucket++) {
-		link_t *cur;
-		link_t *next;
-		
-		for (cur = h->table[bucket].head.next;
-		    cur != &h->table[bucket].head;
-		    cur = next) {
-			next = cur->next;
-			list_append(cur, &new_table[h->hash(cur) % new_size]);
-		}
-	}
-	
-	list_t *old_table = h->table;
-	h->table = new_table;
-	free(old_table);
-	h->size = new_size;
-}
-
-/** Insert item into the set.
- *
- * If the set already contains equivalent object,
- * the function fails.
- *
- * @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 True if the object was inserted
- * @return Ffalse if the set already contained equivalent object.
- *
- */
-int hash_set_insert(hash_set_t *h, link_t *item)
-{
-	assert(item);
-	assert(h);
-	assert(h->hash);
-	assert(h->equals);
-	
-	unsigned long hash = h->hash(item);
-	unsigned long chain = hash % h->size;
-	
-	list_foreach(h->table[chain], cur) {
-		if (h->equals(cur, item))
-			return false;
-	}
-	
-	if (h->count + 1 > h->size) {
-		size_t new_size = h->size * 2;
-		list_t *temp = malloc(new_size * sizeof(list_t));
-		if (temp != NULL)
-			hash_set_rehash(h, temp, new_size);
-		
-		/*
-		 * If the allocation fails, just use the same
-		 * old table and try to rehash next time.
-		 */
-		chain = hash % h->size;
-	}
-	
-	h->count++;
-	list_append(item, &h->table[chain]);
-	
-	return true;
-}
-
-/** Search the hash set for a matching object and return it
- *
- * @param h    Hash set
- * @param item The item that should equal to the matched object
- *
- * @return Matching item on success, NULL if there is no such item.
- *
- */
-link_t *hash_set_find(hash_set_t *h, const link_t *item)
-{
-	assert(h);
-	assert(h->hash);
-	assert(h->equals);
-	
-	unsigned long chain = h->hash(item) % h->size;
-	
-	list_foreach(h->table[chain], cur) {
-		if (h->equals(cur, item))
-			return cur;
-	}
-	
-	return NULL;
-}
-
-/** Remove first matching object from the hash set and return it
- *
- * @param h    Hash set.
- * @param item The item that should be equal to the matched object
- *
- * @return The removed item or NULL if this is not found.
- *
- */
-link_t *hash_set_remove(hash_set_t *h, const link_t *item)
-{
-	assert(h);
-	assert(h->hash);
-	assert(h->equals);
-	
-	link_t *cur = hash_set_find(h, item);
-	if (cur) {
-		list_remove(cur);
-		
-		h->count--;
-		if (4 * h->count < h->size && h->size > HASH_SET_MIN_SIZE) {
-			size_t new_size = h->size / 2;
-			if (new_size < HASH_SET_MIN_SIZE)
-				/* possible e.g. if init_size == HASH_SET_MIN_SIZE + 1 */
-				new_size = HASH_SET_MIN_SIZE;
-			
-			list_t *temp = malloc(new_size * sizeof (list_t));
-			if (temp != NULL)
-				hash_set_rehash(h, temp, new_size);
-		}
-	}
-	
-	return cur;
-}
-
-/** Remove all elements for which the function returned non-zero
- *
- * The function can also destroy the element.
- *
- * @param h   Hash set.
- * @param f   Function to be applied.
- * @param arg Argument to be passed to the function.
- *
- */
-void hash_set_remove_selected(hash_set_t *h, int (*f)(link_t *, void *),
-    void *arg)
-{
-	assert(h);
-	assert(h->table);
-	
-	for (size_t bucket = 0; bucket < h->size; bucket++) {
-		link_t *prev = &h->table[bucket].head;
-		link_t *cur;
-		link_t *next;
-		
-		for (cur = h->table[bucket].head.next;
-		    cur != &h->table[bucket].head;
-		    cur = next) {
-			next = cur->next;
-			if (f(cur, arg)) {
-				prev->next = next;
-				next->prev = prev;
-				h->count--;
-			} else
-				prev = cur;
-		}
-	}
-	
-	if (4 * h->count < h->size && h->size > HASH_SET_MIN_SIZE) {
-		size_t new_size = h->size / 2;
-		if (new_size < HASH_SET_MIN_SIZE)
-			/* possible e.g. if init_size == HASH_SET_MIN_SIZE + 1 */
-			new_size = HASH_SET_MIN_SIZE;
-		
-		list_t *temp = malloc(new_size * sizeof (list_t));
-		if (temp != NULL)
-			hash_set_rehash(h, temp, new_size);
-	}
-}
-
-/** Apply function to all items in hash set
- *
- * @param h   Hash set.
- * @param f   Function to be applied.
- * @param arg Argument to be passed to the function.
- *
- */
-void hash_set_apply(hash_set_t *h, void (*f)(link_t *, void *), void *arg)
-{
-	assert(h);
-	assert(h->table);
-	
-	for (size_t bucket = 0; bucket < h->size; bucket++) {
-		link_t *cur;
-		link_t *next;
-		
-		for (cur = h->table[bucket].head.next;
-		    cur != &h->table[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);
-		}
-	}
-}
-
-/** Remove all elements from the set.
- *
- * The table is reallocated to the minimum size.
- *
- * @param h   Hash set
- * @param f   Function (destructor?) applied to all element. Can be NULL.
- * @param arg Argument to the destructor.
- *
- */
-void hash_set_clear(hash_set_t *h, void (*f)(link_t *, void *), void *arg)
-{
-	assert(h);
-	assert(h->table);
-	
-	for (size_t bucket = 0; bucket < h->size; bucket++) {
-		link_t *cur;
-		link_t *next;
-		
-		for (cur = h->table[bucket].head.next;
-		    cur != &h->table[bucket].head;
-		    cur = next) {
-			next = cur->next;
-			list_remove(cur);
-			if (f != NULL)
-				f(cur, arg);
-		}
-	}
-	
-	assert(h->size >= HASH_SET_MIN_SIZE);
-	list_t *new_table =
-	    realloc(h->table, HASH_SET_MIN_SIZE * sizeof(list_t));
-	
-	/* We are shrinking, therefore we shouldn't get NULL */
-	assert(new_table);
-	
-	if (h->table != new_table) {
-		/* Init the lists, pointers to itself are used in them */
-		for (size_t bucket = 0; bucket < HASH_SET_MIN_SIZE; ++bucket)
-			list_initialize(&new_table[bucket]);
-		
-		h->table = new_table;
-	}
-	
-	h->count = 0;
-	h->size = HASH_SET_MIN_SIZE;
-}
-
-/** Get hash set size
- *
- * @param hHash set
- *
- * @return Number of elements in the set.
- *
- */
-size_t hash_set_count(const hash_set_t *h)
-{
-	assert(h);
-	return h->count;
-}
-
-/** Check whether element is contained in the hash set
- *
- * @param h    Hash set
- * @param item Item that should be equal to the matched object
- *
- * @return True if the hash set contains equal object
- * @return False otherwise
- *
- */
-int hash_set_contains(const hash_set_t *h, const link_t *item)
-{
-	/*
-	 * The hash_set_find cannot accept constant hash set,
-	 * because we can modify the returned element. But in
-	 * this case we are using it safely.
-	 */
-	return hash_set_find((hash_set_t *) h, item) != NULL;
-}
-
-/** @}
- */
Index: uspace/lib/c/generic/adt/hash_table.c
===================================================================
--- uspace/lib/c/generic/adt/hash_table.c	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/lib/c/generic/adt/hash_table.c	(revision 062d9000625057300f609429080872d6492b542e)
@@ -1,4 +1,6 @@
 /*
  * Copyright (c) 2008 Jakub Jermar
+ * Copyright (c) 2012 Adam Hraska
+ * 
  * All rights reserved.
  *
@@ -34,5 +36,15 @@
 
 /*
- * 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,38 +56,99 @@
 #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 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(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 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_load,
+    hash_table_ops_t *op)
 {
 	assert(h);
-	assert(op && op->hash && op->compare);
-	assert(max_keys > 0);
-	
-	h->entry = malloc(m * sizeof(list_t));
-	if (!h->entry)
+	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;
 	
-	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->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;
+	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
  *
@@ -84,29 +157,32 @@
 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;
+	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);
-		}
-	}
-}
-
-/** Destroy a hash table instance.
- *
- * @param h Hash table to be destroyed.
- *
- */
-void hash_table_destroy(hash_table_t *h)
-{
-	assert(h);
-	assert(h->entry);
-	
-	free(h->entry);
+			h->op->remove_callback(cur_link);
+		}
+	}
+	
+	h->item_cnt = 0;
 }
 
@@ -117,13 +193,52 @@
  * @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, ht_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->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 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, 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], cur) {
+		/* 
+		 * We could filter out items using their hashes first, but 
+		 * calling equal() might very well be just as fast.
+		 */
+		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->link, &h->bucket[idx]);
+	++h->item_cnt;
+	grow_if_needed(h);
+	
+	return true;
 }
 
@@ -136,20 +251,45 @@
  *
  */
-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.
-			 */
-			return cur;
-		}
-	}
-	
+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->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;
 }
@@ -163,76 +303,170 @@
  *             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 &&
-	    h->op->remove_callback);
-	assert(keys <= h->max_keys);
-	
-	if (keys == h->max_keys) {
-		/*
-		 * All keys are known, hash_table_find() can be used to find the
-		 * entry.
+ * 
+ * @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!).
+			 */
+			if (!f(cur_link, arg))
+				return;
+		}
+	}
+	
+	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);
+		
+	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;
+}
+
+
+/** 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.
 		 */
-		
-		link_t *cur = hash_table_find(h, key);
-		if (cur) {
-			list_remove(cur);
-			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.
-	 */
-	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;
+	
+	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]);
 			}
 		}
 	}
-}
-
-/** 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);
-		}
-	}
-}
+	
+	free(h->bucket);
+	h->bucket = new_buckets;
+	h->bucket_cnt = new_bucket_cnt;
+	h->full_item_cnt = h->max_load * h->bucket_cnt;
+}
+
 
 /** @}
Index: uspace/lib/c/generic/async.c
===================================================================
--- uspace/lib/c/generic/async.c	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/lib/c/generic/async.c	(revision 062d9000625057300f609429080872d6492b542e)
@@ -116,6 +116,4 @@
 #include "private/libc.h"
 
-#define CLIENT_HASH_TABLE_BUCKETS  32
-#define CONN_HASH_TABLE_BUCKETS    32
 
 /** Session data */
@@ -205,5 +203,5 @@
 /* Client connection data */
 typedef struct {
-	link_t link;
+	ht_link_t link;
 	
 	task_id_t in_task_id;
@@ -217,5 +215,5 @@
 	
 	/** Hash table link. */
-	link_t link;
+	ht_link_t link;
 	
 	/** Incoming client task ID. */
@@ -393,31 +391,31 @@
 static LIST_INITIALIZE(timeout_list);
 
-static hash_index_t client_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)
-{
-	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 void client_remove(link_t *item)
-{
-}
+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;
+}
+
 
 /** 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,
+	.key_equal = client_key_equal,
+	.equal = 0,
+	.remove_callback = 0
 };
 
@@ -429,38 +427,31 @@
  *
  */
-static hash_index_t conn_hash(unsigned long key[])
-{
-	assert(key);
-	
-	return (((key[0]) >> 4) % CONN_HASH_TABLE_BUCKETS);
-}
-
-/** 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 int conn_compare(unsigned long key[], hash_count_t keys, 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 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. */
-static hash_table_operations_t conn_hash_table_ops = {
+static hash_table_ops_t conn_hash_table_ops = {
 	.hash = conn_hash,
-	.compare = conn_compare,
-	.remove_callback = conn_remove
+	.key_hash = conn_key_hash,
+	.key_equal = conn_key_equal,
+	.equal = 0,
+	.remove_callback = 0
 };
 
@@ -510,6 +501,5 @@
 	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) {
@@ -518,5 +508,5 @@
 	}
 	
-	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));
@@ -698,14 +688,10 @@
 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) {
@@ -716,5 +702,5 @@
 		
 			atomic_set(&client->refcnt, 1);
-			hash_table_insert(&client_hash_table, key, &client->link);
+			hash_table_insert(&client_hash_table, &client->link);
 		}
 	}
@@ -727,13 +713,9 @@
 {
 	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
@@ -831,6 +813,5 @@
 	 */
 	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);
 	
@@ -916,8 +897,7 @@
 	
 	/* 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);
 	
@@ -1111,10 +1091,8 @@
 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, 0, &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, 0, &conn_hash_table_ops))
 		abort();
 	
Index: uspace/lib/c/include/adt/hash.h
===================================================================
--- uspace/lib/c/include/adt/hash.h	(revision 062d9000625057300f609429080872d6492b542e)
+++ uspace/lib/c/include/adt/hash.h	(revision 062d9000625057300f609429080872d6492b542e)
@@ -0,0 +1,112 @@
+/*
+ * Copyright (c) 2012 Adam Hraska
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ * - Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in the
+ *   documentation and/or other materials provided with the distribution.
+ * - The name of the author may not be used to endorse or promote products
+ *   derived from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/** @addtogroup genericadt
+ * @{
+ */
+/** @file
+ */
+#ifndef KERN_HASH_H_
+#define KERN_HASH_H_
+
+#include <stdint.h>
+
+/** Produces a uniform hash affecting all output bits from the skewed input. */
+static inline uint32_t hash_mix32(uint32_t hash)
+{
+	/*
+	 * Thomas Wang's modification of Bob Jenkin's hash mixing function:
+	 * http://www.concentric.net/~Ttwang/tech/inthash.htm
+	 * Public domain.
+	 */
+	hash = ~hash + (hash << 15); 
+	hash = hash ^ (hash >> 12);
+	hash = hash + (hash << 2);
+	hash = hash ^ (hash >> 4);
+	hash = hash * 2057; 
+	hash = hash ^ (hash >> 16);
+	return hash;	
+}
+
+/** Produces a uniform hash affecting all output bits from the skewed input. */
+static inline uint64_t hash_mix64(uint64_t hash)
+{
+	/*
+	 * Thomas Wang's public domain 64-bit hash mixing function:
+	 * http://www.concentric.net/~Ttwang/tech/inthash.htm
+	 */
+	hash = (hash ^ 61) ^ (hash >> 16);
+	hash = hash + (hash << 3);
+	hash = hash ^ (hash >> 4);
+	hash = hash * 0x27d4eb2d;
+	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
+	 * more usable.
+	 */
+	return (hash << 32) | (hash >> 32);
+}
+
+/** Produces a uniform hash affecting all output bits from the skewed input. */
+static inline size_t hash_mix(size_t hash) 
+{
+#ifdef __32_BITS__
+	return hash_mix32(hash);
+#elif defined(__64_BITS__)
+	return hash_mix64(hash);
+#else
+#error Unknown size_t size - cannot select proper hash mix function.
+#endif
+}
+
+/** Use to create a hash from multiple values.
+ * 
+ * Typical usage:
+ * @code
+ * int car_id;
+ * bool car_convertible;
+ * // ..
+ * size_t hash = 0;
+ * hash = hash_combine(hash, car_id);
+ * hash = hash_combine(hash, car_convertible);
+ * // Now use hash as a hash of both car_id and car_convertible.
+ * @endcode
+ */
+static inline size_t hash_combine(size_t seed, size_t hash)
+{
+	/* 
+	 * todo: use Bob Jenkin's proper mixing hash pass:
+	 * http://burtleburtle.net/bob/c/lookup3.c
+	 */
+	seed ^= hash + 0x9e3779b9 
+		+ ((seed << 5) | (seed >> (sizeof(size_t) * 8 - 5)));
+	return seed;	
+}
+
+#endif
Index: pace/lib/c/include/adt/hash_set.h
===================================================================
--- uspace/lib/c/include/adt/hash_set.h	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ 	(revision )
@@ -1,84 +1,0 @@
-/*
- * Copyright (c) 2006 Jakub Jermar
- * Copyright (c) 2011 Radim Vansa
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- *
- * - Redistributions of source code must retain the above copyright
- *   notice, this list of conditions and the following disclaimer.
- * - Redistributions in binary form must reproduce the above copyright
- *   notice, this list of conditions and the following disclaimer in the
- *   documentation and/or other materials provided with the distribution.
- * - The name of the author may not be used to endorse or promote products
- *   derived from this software without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
- * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
- * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
- * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
- * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
- * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
- * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
- * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
- * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- */
-
-/** @addtogroup libc
- * @{
- */
-/** @file
- */
-
-#ifndef LIBC_HASH_SET_H_
-#define LIBC_HASH_SET_H_
-
-#include <adt/list.h>
-#include <unistd.h>
-
-#define HASH_SET_MIN_SIZE  8
-
-typedef unsigned long (*hash_set_hash)(const link_t *);
-typedef int (*hash_set_equals)(const link_t *, const link_t *);
-
-/** Hash table structure. */
-typedef struct {
-	list_t *table;
-	
-	/** Current table size */
-	size_t size;
-	
-	/**
-	 * Current number of entries. If count > size,
-	 * the table is rehashed into table with double
-	 * size. If (4 * count < size) && (size > min_size),
-	 * the table is rehashed into table with half the size.
-	 */
-	size_t count;
-	
-	/** Hash function */
-	hash_set_hash hash;
-	
-	/** Hash table item equals function */
-	hash_set_equals equals;
-} hash_set_t;
-
-extern int hash_set_init(hash_set_t *, hash_set_hash, hash_set_equals, size_t);
-extern int hash_set_insert(hash_set_t *, link_t *);
-extern link_t *hash_set_find(hash_set_t *, const link_t *);
-extern int hash_set_contains(const hash_set_t *, const link_t *);
-extern size_t hash_set_count(const hash_set_t *);
-extern link_t *hash_set_remove(hash_set_t *, const link_t *);
-extern void hash_set_remove_selected(hash_set_t *,
-    int (*)(link_t *, void *), void *);
-extern void hash_set_destroy(hash_set_t *);
-extern void hash_set_apply(hash_set_t *, void (*)(link_t *, void *), void *);
-extern void hash_set_clear(hash_set_t *, void (*)(link_t *, void *), void *);
-
-#endif
-
-/** @}
- */
Index: uspace/lib/c/include/adt/hash_table.h
===================================================================
--- uspace/lib/c/include/adt/hash_table.h	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/lib/c/include/adt/hash_table.h	(revision 062d9000625057300f609429080872d6492b542e)
@@ -1,4 +1,6 @@
 /*
  * Copyright (c) 2006 Jakub Jermar
+ * Copyright (c) 2012 Adam Hraska
+ * 
  * All rights reserved.
  *
@@ -39,58 +41,65 @@
 #include <unistd.h>
 #include <bool.h>
+#include <macros.h>
 
-typedef unsigned long hash_count_t;
-typedef unsigned long hash_index_t;
+/** 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.
-	 *
-	 */
-	hash_index_t (*hash)(unsigned long 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.
-	 *
-	 */
-	int (*compare)(unsigned long key[], hash_count_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;
-	hash_count_t entries;
-	hash_count_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 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_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 *, unsigned long [], 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 void hash_table_destroy(hash_table_t *);
-extern void hash_table_apply(hash_table_t *, void (*)(link_t *, void *),
-    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 *);
+
 
 #endif
Index: uspace/lib/c/include/adt/list.h
===================================================================
--- uspace/lib/c/include/adt/list.h	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/lib/c/include/adt/list.h	(revision 062d9000625057300f609429080872d6492b542e)
@@ -71,6 +71,43 @@
 	    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))
+
+/** 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
Index: uspace/lib/c/include/macros.h
===================================================================
--- uspace/lib/c/include/macros.h	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/lib/c/include/macros.h	(revision 062d9000625057300f609429080872d6492b542e)
@@ -52,4 +52,10 @@
 	    | ((((uint64_t) (up)) & 0xffffffff) << 32))
 
+#ifndef member_to_inst
+#define member_to_inst(ptr_member, type, member_identif) \
+	((type*) (((void*)(ptr_member)) - ((void*)&(((type*)0)->member_identif))))
+#endif
+
+
 #endif
 
Index: uspace/lib/nic/include/nic.h
===================================================================
--- uspace/lib/nic/include/nic.h	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/lib/nic/include/nic.h	(revision 062d9000625057300f609429080872d6492b542e)
@@ -40,4 +40,5 @@
 
 #include <adt/list.h>
+#include <adt/hash_table.h>
 #include <ddf/driver.h>
 #include <device/hw_res_parsed.h>
@@ -53,5 +54,5 @@
  */
 typedef struct nic_wol_virtue {
-	link_t item;
+	ht_link_t item;
 	nic_wv_id_t id;
 	nic_wv_type_t type;
Index: uspace/lib/nic/include/nic_addr_db.h
===================================================================
--- uspace/lib/nic/include/nic_addr_db.h	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/lib/nic/include/nic_addr_db.h	(revision 062d9000625057300f609429080872d6492b542e)
@@ -43,14 +43,5 @@
 #endif
 
-#include <adt/hash_set.h>
-
-/**
- * Initial size of DB's hash set
- */
-#define NIC_ADDR_DB_INIT_SIZE 	8
-/**
- * Maximal length of addresses in the DB (in bytes).
- */
-#define NIC_ADDR_MAX_LENGTH		16
+#include <adt/hash_table.h>
 
 /**
@@ -58,25 +49,14 @@
  */
 typedef struct nic_addr_db {
-	hash_set_t set;
+	hash_table_t set;
 	size_t addr_len;
 } nic_addr_db_t;
 
-/**
- * Helper structure for keeping the address in the hash set.
- */
-typedef struct nic_addr_entry {
-	link_t item;
-	size_t addr_len;
-	uint8_t addr[NIC_ADDR_MAX_LENGTH];
-} nic_addr_entry_t;
 
 extern int nic_addr_db_init(nic_addr_db_t *db, size_t addr_len);
 extern void nic_addr_db_clear(nic_addr_db_t *db);
 extern void nic_addr_db_destroy(nic_addr_db_t *db);
-extern size_t nic_addr_db_count(const nic_addr_db_t *db);
 extern int nic_addr_db_insert(nic_addr_db_t *db, const uint8_t *addr);
 extern int nic_addr_db_remove(nic_addr_db_t *db, const uint8_t *addr);
-extern void nic_addr_db_remove_selected(nic_addr_db_t *db,
-	int (*func)(const uint8_t *, void *), void *arg);
 extern int nic_addr_db_contains(const nic_addr_db_t *db, const uint8_t *addr);
 extern void nic_addr_db_foreach(const nic_addr_db_t *db,
Index: uspace/lib/nic/include/nic_wol_virtues.h
===================================================================
--- uspace/lib/nic/include/nic_wol_virtues.h	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/lib/nic/include/nic_wol_virtues.h	(revision 062d9000625057300f609429080872d6492b542e)
@@ -51,5 +51,5 @@
 	 * Operations for table
 	 */
-	hash_table_operations_t table_operations;
+	hash_table_ops_t table_operations;
 	/**
 	 * WOL virtues hashed by their ID's.
Index: uspace/lib/nic/src/nic_addr_db.c
===================================================================
--- uspace/lib/nic/src/nic_addr_db.c	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/lib/nic/src/nic_addr_db.c	(revision 062d9000625057300f609429080872d6492b542e)
@@ -35,4 +35,6 @@
  * @brief Generic hash-set based database of addresses
  */
+#include "nic_addr_db.h"
+#include "libarch/common.h"
 #include <assert.h>
 #include <stdlib.h>
@@ -40,49 +42,72 @@
 #include <errno.h>
 #include <mem.h>
-
-#include "nic_addr_db.h"
-
-/**
- * Hash set helper function
- */
-static int nic_addr_equals(const link_t *item1, const link_t *item2)
-{
-	assert(item1 && item2);
-	size_t addr_len = ((const nic_addr_entry_t *) item1)->addr_len;
-
-	assert(addr_len	== ((const nic_addr_entry_t *) item2)->addr_len);
-
-	size_t i;
-	for (i = 0; i < addr_len; ++i) {
-		if (((nic_addr_entry_t *) item1)->addr[i] !=
-			((nic_addr_entry_t *) item2)->addr[i])
-			return false;
+#include <adt/hash_table.h>
+#include <macros.h>
+#include <stdint.h>
+
+
+/**
+ * Helper structure for keeping the address in the hash set.
+ */
+typedef struct nic_addr_entry {
+	ht_link_t link;
+	uint8_t len;
+	uint8_t addr[1];
+} nic_addr_entry_t;
+
+
+/* 
+ * Hash table helper functions 
+ */
+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 (size_t i = 0; i < len; ++i) {
+		hash = (hash << 5) ^ addr[i];
 	}
-	return true;
-}
-
-/**
- * Hash set helper function
- */
-static unsigned long nic_addr_hash(const link_t *item)
-{
-	assert(item);
-	const nic_addr_entry_t *entry = (const nic_addr_entry_t *) item;
-	unsigned long hash = 0;
-
-	size_t i;
-	for (i = 0; i < entry->addr_len; ++i) {
-		hash = (hash << 8) ^ (hash >> 24) ^ entry->addr[i];
-	}
+	
 	return hash;
 }
 
-/**
- * Helper wrapper
- */
-static void nic_addr_destroy(link_t *item, void *unused)
-{
-	free(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);
+	
+	free(entry);
+}
+
+static hash_table_ops_t set_ops = {
+	.hash = nic_addr_hash,
+	.key_hash = nic_addr_key_hash,
+	.key_equal = nic_addr_key_equal,
+	.equal = 0,
+	.remove_callback = nic_addr_removed
+};
 
 /**
@@ -99,11 +124,11 @@
 {
 	assert(db);
-	if (addr_len > NIC_ADDR_MAX_LENGTH) {
+	
+	if (addr_len > UCHAR_MAX)
 		return EINVAL;
-	}
-	if (!hash_set_init(&db->set, nic_addr_hash, nic_addr_equals,
-		NIC_ADDR_DB_INIT_SIZE)) {
+	
+	if (!hash_table_create(&db->set, 0, 0, &set_ops))
 		return ENOMEM;
-	}
+	
 	db->addr_len = addr_len;
 	return EOK;
@@ -118,5 +143,5 @@
 {
 	assert(db);
-	hash_set_clear(&db->set, nic_addr_destroy, NULL);
+	hash_table_clear(&db->set);
 }
 
@@ -129,20 +154,7 @@
 {
 	assert(db);
-	hash_set_apply(&db->set, nic_addr_destroy, NULL);
-	hash_set_destroy(&db->set);
-}
-
-/**
- * Get number of addresses in the db
- *
- * @param	db
- *
- * @return Number of adresses
- */
-size_t nic_addr_db_count(const nic_addr_db_t *db)
-{
-	assert(db);
-	return hash_set_count(&db->set);
-}
+	hash_table_destroy(&db->set);
+}
+
 
 /**
@@ -160,12 +172,22 @@
 {
 	assert(db && addr);
-	nic_addr_entry_t *entry = malloc(sizeof (nic_addr_entry_t));
-	if (entry == NULL) {
+
+	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) + db->addr_len - 1);
+	if (entry == NULL) 
 		return ENOMEM;
-	}
-	entry->addr_len = db->addr_len;
+
+	entry->len = (uint8_t) db->addr_len;
 	memcpy(entry->addr, addr, db->addr_len);
-
-	return hash_set_insert(&db->set, &entry->item) ? EOK : EEXIST;
+	
+	hash_table_insert(&db->set, &entry->link);
+	return EOK;
 }
 
@@ -182,11 +204,14 @@
 {
 	assert(db && addr);
-	nic_addr_entry_t entry;
-	entry.addr_len = db->addr_len;
-	memcpy(entry.addr, addr, db->addr_len);
-
-	link_t *removed = hash_set_remove(&db->set, &entry.item);
-	free(removed);
-	return removed != NULL ? EOK : ENOENT;
+	
+	addr_key_t key = {
+		.len = db->addr_len,
+		.addr = addr
+	};
+	
+	if (hash_table_remove(&db->set, &key))
+		return EOK;
+	else
+		return ENOENT;
 }
 
@@ -202,9 +227,11 @@
 {
 	assert(db && addr);
-	nic_addr_entry_t entry;
-	entry.addr_len = db->addr_len;
-	memcpy(entry.addr, addr, db->addr_len);
-
-	return hash_set_contains(&db->set, &entry.item);
+	
+	addr_key_t key = {
+		.len = db->addr_len,
+		.addr = addr
+	};
+	
+	return 0 != hash_table_find(&db->set, &key);
 }
 
@@ -220,7 +247,10 @@
  * Helper function for nic_addr_db_foreach
  */
-static void 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;
-	hs->func(((nic_addr_entry_t *) item)->addr, hs->arg);
+	nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link);
+	hs->func(entry->addr, hs->arg);
+	return true;
 }
 
@@ -237,39 +267,5 @@
 {
 	nic_addr_db_fe_arg_t hs = { .func = func, .arg = arg };
-	hash_set_apply((hash_set_t *) &db->set, nic_addr_db_fe_helper, &hs);
-}
-
-/**
- * Helper structure for nic_addr_db_remove_selected
- */
-typedef struct {
-	int (*func)(const uint8_t *, void *);
-	void *arg;
-} nic_addr_db_rs_arg_t;
-
-/**
- * Helper function for nic_addr_db_foreach
- */
-static int nic_addr_db_rs_helper(link_t *item, void *arg) {
-	nic_addr_db_rs_arg_t *hs = (nic_addr_db_rs_arg_t *) arg;
-	int retval = hs->func(((nic_addr_entry_t *) item)->addr, hs->arg);
-	if (retval) {
-		free(item);
-	}
-	return retval;
-}
-
-/**
- * Removes all addresses for which the function returns non-zero.
- *
- * @param	db
- * @param	func	User-defined function
- * @param	arg		Custom argument passed to the function
- */
-void nic_addr_db_remove_selected(nic_addr_db_t *db,
-	int (*func)(const uint8_t *, void *), void *arg)
-{
-	nic_addr_db_rs_arg_t hs = { .func = func, .arg = arg };
-	hash_set_remove_selected(&db->set, nic_addr_db_rs_helper, &hs);
+	hash_table_apply((hash_table_t*)&db->set, nic_addr_db_fe_helper, &hs);
 }
 
Index: uspace/lib/nic/src/nic_wol_virtues.c
===================================================================
--- uspace/lib/nic/src/nic_wol_virtues.c	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/lib/nic/src/nic_wol_virtues.c	(revision 062d9000625057300f609429080872d6492b542e)
@@ -37,32 +37,28 @@
 
 #include "nic_wol_virtues.h"
+#include "nic.h"
 #include <assert.h>
 #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(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;
-	return (virtue->id == (nic_wv_id_t) key[0]);
-}
-
-/**
- * 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;
+	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);
 }
 
@@ -77,10 +73,12 @@
 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.key_equal = nic_wv_key_equal;
+	wvs->table_operations.equal = 0;
+	wvs->table_operations.remove_callback = 0;
+	
+	if (!hash_table_create(&wvs->table, 0, 0, &wvs->table_operations)) {
 		return ENOMEM;
 	}
@@ -170,8 +168,6 @@
 	do {
 		virtue->id = wvs->next_id++;
-	} while (NULL !=
-		hash_table_find(&wvs->table, (unsigned long *) &virtue->id));
-	hash_table_insert(&wvs->table,
-		(unsigned long *) &virtue->id, &virtue->item);
+	} while (NULL != hash_table_find(&wvs->table, &virtue->id));
+	hash_table_insert(&wvs->table, &virtue->item);
 	virtue->next = wvs->lists[virtue->type];
 	wvs->lists[virtue->type] = virtue;
@@ -191,6 +187,6 @@
 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;
@@ -198,5 +194,5 @@
 
 	/* 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 */
@@ -235,6 +231,5 @@
 	 * 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;
 }
Index: uspace/srv/devman/devman.c
===================================================================
--- uspace/srv/devman/devman.c	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/srv/devman/devman.c	(revision 062d9000625057300f609429080872d6492b542e)
@@ -66,50 +66,78 @@
 /* hash table operations */
 
-static hash_index_t devices_hash(unsigned long key[])
-{
-	return key[0] % DEVICE_BUCKETS;
-}
-
-static int devman_devices_compare(unsigned long key[], hash_count_t keys,
-    link_t *item)
-{
-	dev_node_t *dev = hash_table_get_instance(item, dev_node_t, devman_dev);
-	return (dev->handle == (devman_handle_t) key[0]);
-}
-
-static int devman_functions_compare(unsigned long key[], hash_count_t keys,
-    link_t *item)
-{
-	fun_node_t *fun = hash_table_get_instance(item, fun_node_t, devman_fun);
-	return (fun->handle == (devman_handle_t) key[0]);
-}
-
-static int loc_functions_compare(unsigned long key[], hash_count_t keys,
-    link_t *item)
-{
-	fun_node_t *fun = hash_table_get_instance(item, fun_node_t, loc_fun);
-	return (fun->service_id == (service_id_t) key[0]);
-}
-
-static void devices_remove_callback(link_t *item)
-{
-}
-
-static hash_table_operations_t devman_devices_ops = {
-	.hash = devices_hash,
-	.compare = devman_devices_compare,
-	.remove_callback = devices_remove_callback
+static inline size_t handle_key_hash(void *key)
+{
+	devman_handle_t handle = *(devman_handle_t*)key;
+	return handle;
+}
+
+static size_t devman_devices_hash(const ht_link_t *item)
+{
+	dev_node_t *dev = hash_table_get_inst(item, dev_node_t, devman_dev);
+	return handle_key_hash(&dev->handle);
+}
+
+static size_t devman_functions_hash(const ht_link_t *item)
+{
+	fun_node_t *fun = hash_table_get_inst(item, fun_node_t, devman_fun);
+	return handle_key_hash(&fun->handle);
+}
+
+static bool devman_devices_key_equal(void *key, const ht_link_t *item)
+{
+	devman_handle_t handle = *(devman_handle_t*)key;
+	dev_node_t *dev = hash_table_get_inst(item, dev_node_t, devman_dev);
+	return dev->handle == handle;
+}
+
+static bool devman_functions_key_equal(void *key, const ht_link_t *item)
+{
+	devman_handle_t handle = *(devman_handle_t*)key;
+	fun_node_t *fun = hash_table_get_inst(item, fun_node_t, devman_fun);
+	return fun->handle == handle;
+}
+
+static inline size_t service_id_key_hash(void *key)
+{
+	service_id_t service_id = *(service_id_t*)key;
+	return service_id;
+}
+
+static size_t loc_functions_hash(const ht_link_t *item)
+{
+	fun_node_t *fun = hash_table_get_inst(item, fun_node_t, loc_fun);
+	return service_id_key_hash(&fun->service_id);
+}
+
+static bool loc_functions_key_equal(void *key, const ht_link_t *item)
+{
+	service_id_t service_id = *(service_id_t*)key;
+	fun_node_t *fun = hash_table_get_inst(item, fun_node_t, loc_fun);
+	return fun->service_id == service_id;
+}
+
+
+static hash_table_ops_t devman_devices_ops = {
+	.hash = devman_devices_hash,
+	.key_hash = handle_key_hash,
+	.key_equal = devman_devices_key_equal,
+	.equal = 0,
+	.remove_callback = 0
 };
 
-static hash_table_operations_t devman_functions_ops = {
-	.hash = devices_hash,
-	.compare = devman_functions_compare,
-	.remove_callback = devices_remove_callback
+static hash_table_ops_t devman_functions_ops = {
+	.hash = devman_functions_hash,
+	.key_hash = handle_key_hash,
+	.key_equal = devman_functions_key_equal,
+	.equal = 0,
+	.remove_callback = 0
 };
 
-static hash_table_operations_t loc_devices_ops = {
-	.hash = devices_hash,
-	.compare = loc_functions_compare,
-	.remove_callback = devices_remove_callback
+static hash_table_ops_t loc_devices_ops = {
+	.hash = loc_functions_hash,
+	.key_hash = service_id_key_hash,
+	.key_equal = loc_functions_key_equal,
+	.equal = 0,
+	.remove_callback = 0
 };
 
@@ -974,10 +1002,7 @@
 	tree->current_handle = 0;
 	
-	hash_table_create(&tree->devman_devices, DEVICE_BUCKETS, 1,
-	    &devman_devices_ops);
-	hash_table_create(&tree->devman_functions, DEVICE_BUCKETS, 1,
-	    &devman_functions_ops);
-	hash_table_create(&tree->loc_functions, DEVICE_BUCKETS, 1,
-	    &loc_devices_ops);
+	hash_table_create(&tree->devman_devices, 0, 0, &devman_devices_ops);
+	hash_table_create(&tree->devman_functions, 0, 0, &devman_functions_ops);
+	hash_table_create(&tree->loc_functions, 0, 0, &loc_devices_ops);
 	
 	fibril_rwlock_initialize(&tree->rwlock);
@@ -1013,5 +1038,4 @@
 	list_initialize(&dev->functions);
 	link_initialize(&dev->driver_devices);
-	link_initialize(&dev->devman_dev);
 	
 	return dev;
@@ -1060,14 +1084,11 @@
 dev_node_t *find_dev_node_no_lock(dev_tree_t *tree, devman_handle_t handle)
 {
-	unsigned long key = handle;
-	link_t *link;
-	
 	assert(fibril_rwlock_is_locked(&tree->rwlock));
 	
-	link = hash_table_find(&tree->devman_devices, &key);
+	ht_link_t *link = hash_table_find(&tree->devman_devices, &handle);
 	if (link == NULL)
 		return NULL;
 	
-	return hash_table_get_instance(link, dev_node_t, devman_dev);
+	return hash_table_get_inst(link, dev_node_t, devman_dev);
 }
 
@@ -1144,6 +1165,4 @@
 	link_initialize(&fun->dev_functions);
 	list_initialize(&fun->match_ids.ids);
-	link_initialize(&fun->devman_fun);
-	link_initialize(&fun->loc_fun);
 	
 	return fun;
@@ -1206,15 +1225,13 @@
 fun_node_t *find_fun_node_no_lock(dev_tree_t *tree, devman_handle_t handle)
 {
-	unsigned long key = handle;
-	link_t *link;
 	fun_node_t *fun;
 	
 	assert(fibril_rwlock_is_locked(&tree->rwlock));
 	
-	link = hash_table_find(&tree->devman_functions, &key);
+	ht_link_t *link = hash_table_find(&tree->devman_functions, &handle);
 	if (link == NULL)
 		return NULL;
 	
-	fun = hash_table_get_instance(link, fun_node_t, devman_fun);
+	fun = hash_table_get_inst(link, fun_node_t, devman_fun);
 	
 	return fun;
@@ -1294,6 +1311,5 @@
 	/* Add the node to the handle-to-node map. */
 	dev->handle = ++tree->current_handle;
-	unsigned long key = dev->handle;
-	hash_table_insert(&tree->devman_devices, &key, &dev->devman_dev);
+	hash_table_insert(&tree->devman_devices, &dev->devman_dev);
 
 	/* Add the node to the list of its parent's children. */
@@ -1316,6 +1332,5 @@
 	
 	/* Remove node from the handle-to-node map. */
-	unsigned long key = dev->handle;
-	hash_table_remove(&tree->devman_devices, &key, 1);
+	hash_table_remove(&tree->devman_devices, &dev->handle);
 	
 	/* Unlink from parent function. */
@@ -1358,6 +1373,5 @@
 	/* Add the node to the handle-to-node map. */
 	fun->handle = ++tree->current_handle;
-	unsigned long key = fun->handle;
-	hash_table_insert(&tree->devman_functions, &key, &fun->devman_fun);
+	hash_table_insert(&tree->devman_functions, &fun->devman_fun);
 
 	/* Add the node to the list of its parent's children. */
@@ -1379,6 +1393,5 @@
 	
 	/* Remove the node from the handle-to-node map. */
-	unsigned long key = fun->handle;
-	hash_table_remove(&tree->devman_functions, &key, 1);
+	hash_table_remove(&tree->devman_functions, &fun->handle);
 	
 	/* Remove the node from the list of its parent's children. */
@@ -1493,11 +1506,9 @@
 {
 	fun_node_t *fun = NULL;
-	link_t *link;
-	unsigned long key = (unsigned long) service_id;
 	
 	fibril_rwlock_read_lock(&tree->rwlock);
-	link = hash_table_find(&tree->loc_functions, &key);
+	ht_link_t *link = hash_table_find(&tree->loc_functions, &service_id);
 	if (link != NULL) {
-		fun = hash_table_get_instance(link, fun_node_t, loc_fun);
+		fun = hash_table_get_inst(link, fun_node_t, loc_fun);
 		fun_add_ref(fun);
 	}
@@ -1511,6 +1522,5 @@
 	assert(fibril_rwlock_is_write_locked(&tree->rwlock));
 	
-	unsigned long key = (unsigned long) fun->service_id;
-	hash_table_insert(&tree->loc_functions, &key, &fun->loc_fun);
+	hash_table_insert(&tree->loc_functions, &fun->loc_fun);
 }
 
Index: uspace/srv/devman/devman.h
===================================================================
--- uspace/srv/devman/devman.h	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/srv/devman/devman.h	(revision 062d9000625057300f609429080872d6492b542e)
@@ -52,5 +52,4 @@
 
 #define MATCH_EXT ".ma"
-#define DEVICE_BUCKETS 256
 
 #define LOC_DEVICE_NAMESPACE "devices"
@@ -151,5 +150,5 @@
 	 * Used by the hash table of devices indexed by devman device handles.
 	 */
-	link_t devman_dev;
+	ht_link_t devman_dev;
 	
 	/**
@@ -204,10 +203,10 @@
 	 * Used by the hash table of functions indexed by devman device handles.
 	 */
-	link_t devman_fun;
+	ht_link_t devman_fun;
 	
 	/**
 	 * Used by the hash table of functions indexed by service IDs.
 	 */
-	link_t loc_fun;
+	ht_link_t loc_fun;
 };
 
Index: uspace/srv/fs/cdfs/cdfs_ops.c
===================================================================
--- uspace/srv/fs/cdfs/cdfs_ops.c	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/srv/fs/cdfs/cdfs_ops.c	(revision 062d9000625057300f609429080872d6492b542e)
@@ -37,6 +37,8 @@
  */
 
+#include "cdfs_ops.h"
 #include <bool.h>
 #include <adt/hash_table.h>
+#include <adt/hash.h>
 #include <malloc.h>
 #include <mem.h>
@@ -50,21 +52,9 @@
 #include "cdfs.h"
 #include "cdfs_endian.h"
-#include "cdfs_ops.h"
 
 /** Standard CD-ROM block size */
 #define BLOCK_SIZE  2048
 
-/** Implicit node cache size
- *
- * More nodes can be actually cached if the files remain
- * opended.
- *
- */
-#define NODE_CACHE_SIZE  200
-
-#define NODES_BUCKETS  256
-
-#define NODES_KEY_SRVC   0
-#define NODES_KEY_INDEX  1
+#define NODE_CACHE_SIZE 200
 
 /** All root nodes have index 0 */
@@ -205,5 +195,5 @@
 	service_id_t service_id;  /**< Service ID of block device */
 	
-	link_t nh_link;           /**< Nodes hash table link */
+	ht_link_t nh_link;        /**< Nodes hash table link */
 	cdfs_dentry_type_t type;  /**< Dentry type */
 	
@@ -226,31 +216,36 @@
 static hash_table_t nodes;
 
-static hash_index_t nodes_hash(unsigned long key[])
-{
-	return key[NODES_KEY_INDEX] % NODES_BUCKETS;
-}
-
-static int nodes_compare(unsigned long key[], hash_count_t keys, link_t *item)
-{
-	cdfs_node_t *node =
-	    hash_table_get_instance(item, cdfs_node_t, nh_link);
-	
-	switch (keys) {
-	case 1:
-		return (node->service_id == key[NODES_KEY_SRVC]);
-	case 2:
-		return ((node->service_id == key[NODES_KEY_SRVC]) &&
-		    (node->index == key[NODES_KEY_INDEX]));
-	default:
-		assert((keys == 1) || (keys == 2));
-	}
-	
-	return 0;
-}
-
-static void nodes_remove_callback(link_t *item)
-{
-	cdfs_node_t *node =
-	    hash_table_get_instance(item, cdfs_node_t, nh_link);
+/* 
+ * Hash table support functions.
+ */
+
+typedef struct {
+	service_id_t service_id;
+    fs_index_t index;
+} ht_key_t;
+
+static size_t nodes_key_hash(void *k)
+{
+	ht_key_t *key = (ht_key_t*)k;
+	return hash_combine(key->service_id, key->index);
+}
+
+static size_t nodes_hash(const ht_link_t *item)
+{
+	cdfs_node_t *node = hash_table_get_inst(item, cdfs_node_t, nh_link);
+	return hash_combine(node->service_id, node->index);
+}
+
+static bool nodes_key_equal(void *k, const ht_link_t *item)
+{
+	cdfs_node_t *node = hash_table_get_inst(item, cdfs_node_t, nh_link);
+	ht_key_t *key = (ht_key_t*)k;
+	
+	return key->service_id == node->service_id && key->index == node->index;
+}
+
+static void nodes_remove_callback(ht_link_t *item)
+{
+	cdfs_node_t *node = hash_table_get_inst(item, cdfs_node_t, nh_link);
 	
 	assert(node->type == CDFS_DIRECTORY);
@@ -268,7 +263,9 @@
 
 /** Nodes hash table operations */
-static hash_table_operations_t nodes_ops = {
+static hash_table_ops_t nodes_ops = {
 	.hash = nodes_hash,
-	.compare = nodes_compare,
+	.key_hash = nodes_key_hash,
+	.key_equal = nodes_key_equal,
+	.equal = 0,
 	.remove_callback = nodes_remove_callback
 };
@@ -277,13 +274,13 @@
     fs_index_t index)
 {
-	unsigned long key[] = {
-		[NODES_KEY_SRVC] = service_id,
-		[NODES_KEY_INDEX] = index
+	ht_key_t key = {
+		.index = index,
+		.service_id = service_id
 	};
 	
-	link_t *link = hash_table_find(&nodes, key);
+	ht_link_t *link = hash_table_find(&nodes, &key);
 	if (link) {
 		cdfs_node_t *node =
-		    hash_table_get_instance(link, cdfs_node_t, nh_link);
+		    hash_table_get_inst(link, cdfs_node_t, nh_link);
 		
 		*rfn = FS_NODE(node);
@@ -311,5 +308,4 @@
 	node->opened = 0;
 	
-	link_initialize(&node->nh_link);
 	list_initialize(&node->cs_list);
 }
@@ -353,10 +349,5 @@
 	
 	/* Insert the new node into the nodes hash table. */
-	unsigned long key[] = {
-		[NODES_KEY_SRVC] = node->service_id,
-		[NODES_KEY_INDEX] = node->index
-	};
-	
-	hash_table_insert(&nodes, key, &node->nh_link);
+	hash_table_insert(&nodes, &node->nh_link);
 	
 	*rfn = FS_NODE(node);
@@ -508,13 +499,13 @@
 static fs_node_t *get_cached_node(service_id_t service_id, fs_index_t index)
 {
-	unsigned long key[] = {
-		[NODES_KEY_SRVC] = service_id,
-		[NODES_KEY_INDEX] = index
+	ht_key_t key = {
+		.index = index,
+		.service_id = service_id
 	};
 	
-	link_t *link = hash_table_find(&nodes, key);
+	ht_link_t *link = hash_table_find(&nodes, &key);
 	if (link) {
 		cdfs_node_t *node =
-		    hash_table_get_instance(link, cdfs_node_t, nh_link);
+		    hash_table_get_inst(link, cdfs_node_t, nh_link);
 		return FS_NODE(node);
 	}
@@ -802,11 +793,19 @@
 }
 
+static bool rm_service_id_nodes(ht_link_t *item, void *arg) 
+{
+	service_id_t service_id = *(service_id_t*)arg;
+	cdfs_node_t *node = hash_table_get_inst(item, cdfs_node_t, nh_link);
+	
+	if (node->service_id == service_id) {
+		hash_table_remove_item(&nodes, &node->nh_link);
+	}
+	
+	return true;
+}
+
 static void cdfs_instance_done(service_id_t service_id)
 {
-	unsigned long key[] = {
-		[NODES_KEY_SRVC] = service_id
-	};
-	
-	hash_table_remove(&nodes, key, 1);
+	hash_table_apply(&nodes, rm_service_id_nodes, &service_id);
 	block_cache_fini(service_id);
 	block_fini(service_id);
@@ -822,15 +821,15 @@
     size_t *rbytes)
 {
-	unsigned long key[] = {
-		[NODES_KEY_SRVC] = service_id,
-		[NODES_KEY_INDEX] = index
+	ht_key_t key = {
+		.index = index,
+		.service_id = service_id
 	};
 	
-	link_t *link = hash_table_find(&nodes, key);
+	ht_link_t *link = hash_table_find(&nodes, &key);
 	if (link == NULL)
 		return ENOENT;
 	
 	cdfs_node_t *node =
-	    hash_table_get_instance(link, cdfs_node_t, nh_link);
+	    hash_table_get_inst(link, cdfs_node_t, nh_link);
 	
 	if (!node->processed) {
@@ -912,34 +911,31 @@
 }
 
+static bool cache_remove_closed(ht_link_t *item, void *arg)
+{
+	size_t *premove_cnt = (size_t*)arg;
+	
+	/* Some nodes were requested to be removed from the cache. */
+	if (0 < *premove_cnt) {
+		cdfs_node_t *node =	hash_table_get_inst(item, cdfs_node_t, nh_link);
+
+		if (!node->opened) {
+			hash_table_remove_item(&nodes, item);
+			
+			--nodes_cached;
+			--*premove_cnt;
+		}
+	}
+	
+	/* Only continue if more nodes were requested to be removed. */
+	return 0 < *premove_cnt;
+}
+
 static void cleanup_cache(service_id_t service_id)
 {
 	if (nodes_cached > NODE_CACHE_SIZE) {
-		size_t remove = nodes_cached - NODE_CACHE_SIZE;
-		
-		// FIXME: this accesses the internals of the hash table
-		//        and should be rewritten in a clean way
-		
-		for (hash_index_t chain = 0; chain < nodes.entries; chain++) {
-			for (link_t *link = nodes.entry[chain].head.next;
-			    link != &nodes.entry[chain].head;
-			    link = link->next) {
-				if (remove == 0)
-					return;
-				
-				cdfs_node_t *node =
-				    hash_table_get_instance(link, cdfs_node_t, nh_link);
-				if (node->opened == 0) {
-					link_t *tmp = link;
-					link = link->prev;
-					
-					list_remove(tmp);
-					nodes.op->remove_callback(tmp);
-					nodes_cached--;
-					remove--;
-					
-					continue;
-				}
-			}
-		}
+		size_t remove_cnt = nodes_cached - NODE_CACHE_SIZE;
+		
+		if (0 < remove_cnt)
+			hash_table_apply(&nodes, cache_remove_closed, &remove_cnt);
 	}
 }
@@ -951,15 +947,15 @@
 		return EOK;
 	
-	unsigned long key[] = {
-		[NODES_KEY_SRVC] = service_id,
-		[NODES_KEY_INDEX] = index
+	ht_key_t key = {
+		.index = index,
+		.service_id = service_id
 	};
 	
-	link_t *link = hash_table_find(&nodes, key);
+	ht_link_t *link = hash_table_find(&nodes, &key);
 	if (link == 0)
 		return ENOENT;
 	
 	cdfs_node_t *node =
-	    hash_table_get_instance(link, cdfs_node_t, nh_link);
+	    hash_table_get_inst(link, cdfs_node_t, nh_link);
 	
 	assert(node->opened > 0);
@@ -1007,5 +1003,5 @@
 bool cdfs_init(void)
 {
-	if (!hash_table_create(&nodes, NODES_BUCKETS, 2, &nodes_ops))
+	if (!hash_table_create(&nodes, 0, 0, &nodes_ops))
 		return false;
 	
Index: uspace/srv/fs/exfat/exfat.h
===================================================================
--- uspace/srv/fs/exfat/exfat.h	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/srv/fs/exfat/exfat.h	(revision 062d9000625057300f609429080872d6492b542e)
@@ -106,7 +106,7 @@
 typedef struct {
 	/** Used indices (position) hash table link. */
-	link_t		uph_link;
+	ht_link_t		uph_link;
 	/** Used indices (index) hash table link. */
-	link_t		uih_link;
+	ht_link_t		uih_link;
 
 	fibril_mutex_t	lock;
Index: uspace/srv/fs/exfat/exfat_idx.c
===================================================================
--- uspace/srv/fs/exfat/exfat_idx.c	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/srv/fs/exfat/exfat_idx.c	(revision 062d9000625057300f609429080872d6492b542e)
@@ -41,4 +41,5 @@
 #include <str.h>
 #include <adt/hash_table.h>
+#include <adt/hash.h>
 #include <adt/list.h>
 #include <assert.h>
@@ -91,4 +92,5 @@
 	if (lock)
 		fibril_mutex_lock(&unused_lock);
+
 	list_foreach(unused_list, l) {
 		u = list_get_instance(l, unused_t, link);
@@ -112,70 +114,48 @@
 static hash_table_t up_hash;
 
-#define UPH_BUCKETS_LOG	12
-#define UPH_BUCKETS	(1 << UPH_BUCKETS_LOG)
-
-#define UPH_SID_KEY	0
-#define UPH_PFC_KEY	1
-#define UPH_PDI_KEY	2
-
-static hash_index_t pos_hash(unsigned long key[])
-{
-	service_id_t service_id = (service_id_t)key[UPH_SID_KEY];
-	exfat_cluster_t pfc = (exfat_cluster_t)key[UPH_PFC_KEY];
-	unsigned pdi = (unsigned)key[UPH_PDI_KEY];
-
-	hash_index_t h;
-
-	/*
-	 * The least significant half of all bits are the least significant bits
-	 * of the parent node's first cluster.
-	 *
-	 * The least significant half of the most significant half of all bits
-	 * are the least significant bits of the node's dentry index within the
-	 * parent directory node.
-	 *
-	 * The most significant half of the most significant half of all bits
-	 * are the least significant bits of the device handle.
-	 */
-	h = pfc & ((1 << (UPH_BUCKETS_LOG / 2)) - 1);
-	h |= (pdi & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) <<
-	    (UPH_BUCKETS_LOG / 2); 
-	h |= (service_id & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) <<
-	    (3 * (UPH_BUCKETS_LOG / 4));
-
-	return h;
-}
-
-static int pos_compare(unsigned long key[], hash_count_t keys, link_t *item)
-{
-	service_id_t service_id = (service_id_t)key[UPH_SID_KEY];
+typedef struct {
+	service_id_t service_id;
 	exfat_cluster_t pfc;
 	unsigned pdi;
-	exfat_idx_t *fidx = list_get_instance(item, exfat_idx_t, uph_link);
-
-	switch (keys) {
-	case 1:
-		return (service_id == fidx->service_id);
-	case 3:
-		pfc = (exfat_cluster_t) key[UPH_PFC_KEY];
-		pdi = (unsigned) key[UPH_PDI_KEY];
-		return (service_id == fidx->service_id) && (pfc == fidx->pfc) &&
-		    (pdi == fidx->pdi);
-	default:
-		assert((keys == 1) || (keys == 3));
-	}
-
-	return 0;
-}
-
-static void pos_remove_callback(link_t *item)
-{
-	/* nothing to do */
-}
-
-static hash_table_operations_t uph_ops = {
+} pos_key_t;
+
+static inline size_t pos_key_hash(void *key)
+{
+	pos_key_t *pos = (pos_key_t*)key;
+	
+	size_t hash = 0;
+	hash = hash_combine(pos->pfc, pos->pdi);
+	return hash_combine(hash, pos->service_id);
+}
+
+static size_t pos_hash(const ht_link_t *item)
+{
+	exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uph_link);
+	
+	pos_key_t pkey = {
+		.service_id = fidx->service_id,
+		.pfc = fidx->pfc,
+		.pdi = fidx->pdi,
+	};
+	
+	return pos_key_hash(&pkey);
+}
+
+static bool pos_key_equal(void *key, const ht_link_t *item)
+{
+	pos_key_t *pos = (pos_key_t*)key;
+	exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uph_link);
+	
+	return pos->service_id == fidx->service_id
+		&& pos->pdi == fidx->pdi
+		&& pos->pfc == fidx->pfc;
+}
+
+static hash_table_ops_t uph_ops = {
 	.hash = pos_hash,
-	.compare = pos_compare,
-	.remove_callback = pos_remove_callback,
+	.key_hash = pos_key_hash,
+	.key_equal = pos_key_equal,
+	.equal = 0,
+	.remove_callback = 0,
 };
 
@@ -186,54 +166,41 @@
 static hash_table_t ui_hash;
 
-#define UIH_BUCKETS_LOG	12
-#define UIH_BUCKETS	(1 << UIH_BUCKETS_LOG)
-
-#define UIH_SID_KEY	0
-#define UIH_INDEX_KEY	1
-
-static hash_index_t idx_hash(unsigned long key[])
-{
-	service_id_t service_id = (service_id_t)key[UIH_SID_KEY];
-	fs_index_t index = (fs_index_t)key[UIH_INDEX_KEY];
-
-	hash_index_t h;
-
-	h = service_id & ((1 << (UIH_BUCKETS_LOG / 2)) - 1);
-	h |= (index & ((1 << (UIH_BUCKETS_LOG / 2)) - 1)) <<
-	    (UIH_BUCKETS_LOG / 2);
-
-	return h;
-}
-
-static int idx_compare(unsigned long key[], hash_count_t keys, link_t *item)
-{
-	service_id_t service_id = (service_id_t)key[UIH_SID_KEY];
+typedef struct {
+	service_id_t service_id;
 	fs_index_t index;
-	exfat_idx_t *fidx = list_get_instance(item, exfat_idx_t, uih_link);
-
-	switch (keys) {
-	case 1:
-		return (service_id == fidx->service_id);
-	case 2:
-		index = (fs_index_t) key[UIH_INDEX_KEY];
-		return (service_id == fidx->service_id) &&
-		    (index == fidx->index);
-	default:
-		assert((keys == 1) || (keys == 2));
-	}
-
-	return 0;
-}
-
-static void idx_remove_callback(link_t *item)
-{
-	exfat_idx_t *fidx = list_get_instance(item, exfat_idx_t, uih_link);
+} idx_key_t;
+
+static size_t idx_key_hash(void *key_arg)
+{
+	idx_key_t *key = (idx_key_t*)key_arg;
+	return hash_combine(key->service_id, key->index);
+}
+
+static size_t idx_hash(const ht_link_t *item)
+{
+	exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uih_link);
+	return hash_combine(fidx->service_id, fidx->index);
+}
+
+static bool idx_key_equal(void *key_arg, const ht_link_t *item)
+{
+	exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uih_link);
+	idx_key_t *key = (idx_key_t*)key_arg;
+	
+	return key->index == fidx->index && key->service_id == fidx->service_id;
+}
+
+static void idx_remove_callback(ht_link_t *item)
+{
+	exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uih_link);
 
 	free(fidx);
 }
 
-static hash_table_operations_t uih_ops = {
+static hash_table_ops_t uih_ops = {
 	.hash = idx_hash,
-	.compare = idx_compare,
+	.key_hash = idx_key_hash,
+	.key_equal = idx_key_equal,
+	.equal = 0,
 	.remove_callback = idx_remove_callback,
 };
@@ -376,6 +343,4 @@
 	}
 		
-	link_initialize(&fidx->uph_link);
-	link_initialize(&fidx->uih_link);
 	fibril_mutex_initialize(&fidx->lock);
 	fidx->service_id = service_id;
@@ -400,10 +365,5 @@
 	}
 		
-	unsigned long ikey[] = {
-		[UIH_SID_KEY] = service_id,
-		[UIH_INDEX_KEY] = fidx->index,
-	};
-	
-	hash_table_insert(&ui_hash, ikey, &fidx->uih_link);
+	hash_table_insert(&ui_hash, &fidx->uih_link);
 	fibril_mutex_lock(&fidx->lock);
 	fibril_mutex_unlock(&used_lock);
@@ -417,15 +377,15 @@
 {
 	exfat_idx_t *fidx;
-	link_t *l;
-	unsigned long pkey[] = {
-		[UPH_SID_KEY] = service_id,
-		[UPH_PFC_KEY] = pfc,
-		[UPH_PDI_KEY] = pdi,
+	
+	pos_key_t pos_key = {
+		.service_id = service_id,
+		.pfc = pfc,
+		.pdi = pdi,
 	};
 
 	fibril_mutex_lock(&used_lock);
-	l = hash_table_find(&up_hash, pkey);
+	ht_link_t *l = hash_table_find(&up_hash, &pos_key);
 	if (l) {
-		fidx = hash_table_get_instance(l, exfat_idx_t, uph_link);
+		fidx = hash_table_get_inst(l, exfat_idx_t, uph_link);
 	} else {
 		int rc;
@@ -437,14 +397,9 @@
 		}
 		
-		unsigned long ikey[] = {
-			[UIH_SID_KEY] = service_id,
-			[UIH_INDEX_KEY] = fidx->index,
-		};
-	
 		fidx->pfc = pfc;
 		fidx->pdi = pdi;
 
-		hash_table_insert(&up_hash, pkey, &fidx->uph_link);
-		hash_table_insert(&ui_hash, ikey, &fidx->uih_link);
+		hash_table_insert(&up_hash, &fidx->uph_link);
+		hash_table_insert(&ui_hash, &fidx->uih_link);
 	}
 	fibril_mutex_lock(&fidx->lock);
@@ -456,12 +411,6 @@
 void exfat_idx_hashin(exfat_idx_t *idx)
 {
-	unsigned long pkey[] = {
-		[UPH_SID_KEY] = idx->service_id,
-		[UPH_PFC_KEY] = idx->pfc,
-		[UPH_PDI_KEY] = idx->pdi,
-	};
-
-	fibril_mutex_lock(&used_lock);
-	hash_table_insert(&up_hash, pkey, &idx->uph_link);
+	fibril_mutex_lock(&used_lock);
+	hash_table_insert(&up_hash, &idx->uph_link);
 	fibril_mutex_unlock(&used_lock);
 }
@@ -469,12 +418,6 @@
 void exfat_idx_hashout(exfat_idx_t *idx)
 {
-	unsigned long pkey[] = {
-		[UPH_SID_KEY] = idx->service_id,
-		[UPH_PFC_KEY] = idx->pfc,
-		[UPH_PDI_KEY] = idx->pdi,
-	};
-
-	fibril_mutex_lock(&used_lock);
-	hash_table_remove(&up_hash, pkey, 3);
+	fibril_mutex_lock(&used_lock);
+	hash_table_remove_item(&up_hash, &idx->uph_link);
 	fibril_mutex_unlock(&used_lock);
 }
@@ -484,14 +427,14 @@
 {
 	exfat_idx_t *fidx = NULL;
-	link_t *l;
-	unsigned long ikey[] = {
-		[UIH_SID_KEY] = service_id,
-		[UIH_INDEX_KEY] = index,
+
+	idx_key_t idx_key = {
+		.service_id = service_id,
+		.index = index,
 	};
 
 	fibril_mutex_lock(&used_lock);
-	l = hash_table_find(&ui_hash, ikey);
+	ht_link_t *l = hash_table_find(&ui_hash, &idx_key);
 	if (l) {
-		fidx = hash_table_get_instance(l, exfat_idx_t, uih_link);
+		fidx = hash_table_get_inst(l, exfat_idx_t, uih_link);
 		fibril_mutex_lock(&fidx->lock);
 	}
@@ -507,10 +450,8 @@
 void exfat_idx_destroy(exfat_idx_t *idx)
 {
-	unsigned long ikey[] = {
-		[UIH_SID_KEY] = idx->service_id,
-		[UIH_INDEX_KEY] = idx->index,
+	idx_key_t idx_key = {
+		.service_id = idx->service_id,
+		.index = idx->index,
 	};
-	service_id_t service_id = idx->service_id;
-	fs_index_t index = idx->index;
 
 	/* TODO: assert(idx->pfc == FAT_CLST_RES0); */
@@ -523,8 +464,8 @@
 	 * the index hash only.
 	 */
-	hash_table_remove(&ui_hash, ikey, 2);
+	hash_table_remove(&ui_hash, &idx_key);
 	fibril_mutex_unlock(&used_lock);
 	/* Release the VFS index. */
-	exfat_index_free(service_id, index);
+	exfat_index_free(idx_key.service_id, idx_key.index);
 	/* The index structure itself is freed in idx_remove_callback(). */
 }
@@ -532,7 +473,7 @@
 int exfat_idx_init(void)
 {
-	if (!hash_table_create(&up_hash, UPH_BUCKETS, 3, &uph_ops)) 
+	if (!hash_table_create(&up_hash, 0, 0, &uph_ops)) 
 		return ENOMEM;
-	if (!hash_table_create(&ui_hash, UIH_BUCKETS, 2, &uih_ops)) {
+	if (!hash_table_create(&ui_hash, 0, 0, &uih_ops)) {
 		hash_table_destroy(&up_hash);
 		return ENOMEM;
@@ -544,4 +485,5 @@
 {
 	/* We assume the hash tables are empty. */
+	assert(hash_table_empty(&up_hash) && hash_table_empty(&ui_hash));
 	hash_table_destroy(&up_hash);
 	hash_table_destroy(&ui_hash);
@@ -568,13 +510,30 @@
 }
 
+static bool rm_pos_service_id(ht_link_t *item, void *arg)
+{
+	service_id_t service_id = *(service_id_t*)arg;
+	exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uph_link);
+
+	if (fidx->service_id == service_id) {
+		hash_table_remove_item(&up_hash, item);
+	}
+	
+	return true;
+}
+
+static bool rm_idx_service_id(ht_link_t *item, void *arg)
+{
+	service_id_t service_id = *(service_id_t*)arg;
+	exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uih_link);
+
+	if (fidx->service_id == service_id) {
+		hash_table_remove_item(&ui_hash, item);
+	}
+	
+	return true;
+}
+
 void exfat_idx_fini_by_service_id(service_id_t service_id)
 {
-	unsigned long ikey[] = {
-		[UIH_SID_KEY] = service_id 
-	};
-	unsigned long pkey[] = {
-		[UPH_SID_KEY] = service_id 
-	};
-
 	/*
 	 * Remove this instance's index structure from up_hash and ui_hash.
@@ -583,6 +542,6 @@
 	 */
 	fibril_mutex_lock(&used_lock);
-	hash_table_remove(&up_hash, pkey, 1);
-	hash_table_remove(&ui_hash, ikey, 1);
+	hash_table_apply(&up_hash, rm_pos_service_id, &service_id);
+	hash_table_apply(&ui_hash, rm_idx_service_id, &service_id);
 	fibril_mutex_unlock(&used_lock);
 
Index: uspace/srv/fs/exfat/exfat_ops.c
===================================================================
--- uspace/srv/fs/exfat/exfat_ops.c	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/srv/fs/exfat/exfat_ops.c	(revision 062d9000625057300f609429080872d6492b542e)
@@ -54,4 +54,5 @@
 #include <byteorder.h>
 #include <adt/hash_table.h>
+#include <adt/hash.h>
 #include <adt/list.h>
 #include <assert.h>
Index: uspace/srv/fs/ext2fs/ext2fs_ops.c
===================================================================
--- uspace/srv/fs/ext2fs/ext2fs_ops.c	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/srv/fs/ext2fs/ext2fs_ops.c	(revision 062d9000625057300f609429080872d6492b542e)
@@ -49,4 +49,5 @@
 #include <byteorder.h>
 #include <adt/hash_table.h>
+#include <adt/hash.h>
 #include <adt/list.h>
 #include <assert.h>
@@ -62,8 +63,4 @@
 #define EXT2FS_NODE(node)	((node) ? (ext2fs_node_t *) (node)->data : NULL)
 #define EXT2FS_DBG(format, ...) {if (false) printf("ext2fs: %s: " format "\n", __FUNCTION__, ##__VA_ARGS__);}
-#define OPEN_NODES_KEYS 2
-#define OPEN_NODES_DEV_HANDLE_KEY 0
-#define OPEN_NODES_INODE_KEY 1
-#define OPEN_NODES_BUCKETS 256
 
 typedef struct ext2fs_instance {
@@ -78,5 +75,5 @@
 	ext2_inode_ref_t *inode_ref;
 	fs_node_t *fs_node;
-	link_t link;
+	ht_link_t link;
 	unsigned int references;
 } ext2fs_node_t;
@@ -122,36 +119,44 @@
 static FIBRIL_MUTEX_INITIALIZE(open_nodes_lock);
 
-/* Hash table interface for open nodes hash table */
-static hash_index_t open_nodes_hash(unsigned long key[])
-{
-	/* TODO: This is very simple and probably can be improved */
-	return key[OPEN_NODES_INODE_KEY] % OPEN_NODES_BUCKETS;
-}
-
-static int open_nodes_compare(unsigned long key[], hash_count_t keys, 
-    link_t *item)
-{
-	ext2fs_node_t *enode = hash_table_get_instance(item, ext2fs_node_t, link);
-	assert(keys > 0);
-	if (enode->instance->service_id !=
-	    ((service_id_t) key[OPEN_NODES_DEV_HANDLE_KEY])) {
-		return false;
-	}
-	if (keys == 1) {
-		return true;
-	}
-	assert(keys == 2);
-	return (enode->inode_ref->index == key[OPEN_NODES_INODE_KEY]);
-}
-
-static void open_nodes_remove_cb(link_t *link)
-{
-	/* We don't use remove callback for this hash table */
-}
-
-static hash_table_operations_t open_nodes_ops = {
+/* 
+ * Hash table interface for open nodes hash table 
+ */
+
+typedef struct {
+	service_id_t service_id;
+	fs_index_t index;
+} node_key_t;
+
+static size_t open_nodes_key_hash(void *key)
+{
+	node_key_t *node_key = (node_key_t*)key;
+	return hash_combine(node_key->service_id, node_key->index);
+}
+
+static size_t open_nodes_hash(const ht_link_t *item)
+{
+	ext2fs_node_t *enode = hash_table_get_inst(item, ext2fs_node_t, link);
+
+	assert(enode->instance);
+	assert(enode->inode_ref);
+	
+	return hash_combine(enode->instance->service_id, enode->inode_ref->index);
+}
+
+static bool open_nodes_key_equal(void *key, const ht_link_t *item)
+{
+	node_key_t *node_key = (node_key_t*)key;
+	ext2fs_node_t *enode = hash_table_get_inst(item, ext2fs_node_t, link);
+	
+	return node_key->service_id == enode->instance->service_id
+		&& node_key->index == enode->inode_ref->index;
+}
+
+static hash_table_ops_t open_nodes_ops = {
 	.hash = open_nodes_hash,
-	.compare = open_nodes_compare,
-	.remove_callback = open_nodes_remove_cb,
+	.key_hash = open_nodes_key_hash,
+	.key_equal = open_nodes_key_equal,
+	.equal = 0,
+	.remove_callback = 0,
 };
 
@@ -161,6 +166,5 @@
 int ext2fs_global_init(void)
 {
-	if (!hash_table_create(&open_nodes, OPEN_NODES_BUCKETS,
-	    OPEN_NODES_KEYS, &open_nodes_ops)) {
+	if (!hash_table_create(&open_nodes, 0, 0, &open_nodes_ops)) {
 		return ENOMEM;
 	}
@@ -316,12 +320,12 @@
 	
 	/* Check if the node is not already open */
-	unsigned long key[] = {
-		[OPEN_NODES_DEV_HANDLE_KEY] = inst->service_id,
-		[OPEN_NODES_INODE_KEY] = index,
+	node_key_t key = {
+		.service_id = inst->service_id,
+		.index = index
 	};
-	link_t *already_open = hash_table_find(&open_nodes, key);
+	ht_link_t *already_open = hash_table_find(&open_nodes, &key);
 
 	if (already_open) {
-		enode = hash_table_get_instance(already_open, ext2fs_node_t, link);
+		enode = hash_table_get_inst(already_open, ext2fs_node_t, link);
 		*rfn = enode->fs_node;
 		enode->references++;
@@ -357,10 +361,9 @@
 	enode->references = 1;
 	enode->fs_node = node;
-	link_initialize(&enode->link);
 	
 	node->data = enode;
 	*rfn = node;
 	
-	hash_table_insert(&open_nodes, key, &enode->link);
+	hash_table_insert(&open_nodes, &enode->link);
 	inst->open_nodes_count++;
 	
@@ -408,15 +411,15 @@
 int ext2fs_node_put_core(ext2fs_node_t *enode)
 {
-	int rc;
-
-	unsigned long key[] = {
-		[OPEN_NODES_DEV_HANDLE_KEY] = enode->instance->service_id,
-		[OPEN_NODES_INODE_KEY] = enode->inode_ref->index,
+	node_key_t key = {
+		.service_id = enode->instance->service_id,
+		.index = enode->inode_ref->index
 	};
-	hash_table_remove(&open_nodes, key, OPEN_NODES_KEYS);
+
+	hash_table_remove(&open_nodes, &key);
+	
 	assert(enode->instance->open_nodes_count > 0);
 	enode->instance->open_nodes_count--;
 
-	rc = ext2_filesystem_put_inode_ref(enode->inode_ref);
+	int rc = ext2_filesystem_put_inode_ref(enode->inode_ref);
 	if (rc != EOK) {
 		EXT2FS_DBG("ext2_filesystem_put_inode_ref failed");
Index: uspace/srv/fs/ext4fs/ext4fs_ops.c
===================================================================
--- uspace/srv/fs/ext4fs/ext4fs_ops.c	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/srv/fs/ext4fs/ext4fs_ops.c	(revision 062d9000625057300f609429080872d6492b542e)
@@ -42,4 +42,5 @@
 #include <malloc.h>
 #include <adt/hash_table.h>
+#include <adt/hash.h>
 #include <ipc/loc.h>
 #include "ext4fs.h"
@@ -48,11 +49,4 @@
 #define EXT4FS_NODE(node) \
 	((node) ? (ext4fs_node_t *) (node)->data : NULL)
-
-#define OPEN_NODES_KEYS  2
-
-#define OPEN_NODES_DEV_HANDLE_KEY  0
-#define OPEN_NODES_INODE_KEY       1
-
-#define OPEN_NODES_BUCKETS  256
 
 /**
@@ -73,5 +67,5 @@
 	ext4_inode_ref_t *inode_ref;
 	fs_node_t *fs_node;
-	link_t link;
+	ht_link_t link;
 	unsigned int references;
 } ext4fs_node_t;
@@ -115,45 +109,37 @@
 
 /* Hash table interface for open nodes hash table */
-static hash_index_t open_nodes_hash(unsigned long key[])
-{
-	/* TODO: This is very simple and probably can be improved */
-	return key[OPEN_NODES_INODE_KEY] % OPEN_NODES_BUCKETS;
-}
-
-/** Compare given item with values in hash table.
- *
- */
-static int open_nodes_compare(unsigned long key[], hash_count_t keys,
-    link_t *item)
-{
-	assert(keys > 0);
-	
-	ext4fs_node_t *enode =
-	    hash_table_get_instance(item, ext4fs_node_t, link);
-	
-	if (enode->instance->service_id !=
-	    ((service_id_t) key[OPEN_NODES_DEV_HANDLE_KEY]))
-		return false;
-	
-	if (keys == 1)
-		return true;
-	
-	assert(keys == 2);
-	
-	return (enode->inode_ref->index == key[OPEN_NODES_INODE_KEY]);
-}
-
-/** Empty callback to correct hash table initialization.
- *
- */
-static void open_nodes_remove_cb(link_t *link)
-{
-	/* We don't use remove callback for this hash table */
-}
-
-static hash_table_operations_t open_nodes_ops = {
+
+typedef struct {
+	service_id_t service_id;
+	fs_index_t index;
+} node_key_t;
+
+static size_t open_nodes_key_hash(void *key_arg)
+{
+	node_key_t *key = (node_key_t *)key_arg;
+	return hash_combine(key->service_id, key->index);
+}
+
+static size_t open_nodes_hash(const ht_link_t *item)
+{
+	ext4fs_node_t *enode = hash_table_get_inst(item, ext4fs_node_t, link);
+	return hash_combine(enode->instance->service_id, enode->inode_ref->index);	
+}
+
+static bool open_nodes_key_equal(void *key_arg, const ht_link_t *item)
+{
+	node_key_t *key = (node_key_t *)key_arg;
+	ext4fs_node_t *enode = hash_table_get_inst(item, ext4fs_node_t, link);
+	
+	return key->service_id == enode->instance->service_id
+		&& key->index == enode->inode_ref->index;
+}
+
+static hash_table_ops_t open_nodes_ops = {
 	.hash = open_nodes_hash,
-	.compare = open_nodes_compare,
-	.remove_callback = open_nodes_remove_cb,
+	.key_hash = open_nodes_key_hash,
+	.key_equal = open_nodes_key_equal,
+	.equal = NULL,
+	.remove_callback = NULL,
 };
 
@@ -168,6 +154,5 @@
 int ext4fs_global_init(void)
 {
-	if (!hash_table_create(&open_nodes, OPEN_NODES_BUCKETS,
-	    OPEN_NODES_KEYS, &open_nodes_ops))
+	if (!hash_table_create(&open_nodes, 0, 0, &open_nodes_ops))
 		return ENOMEM;
 	
@@ -315,13 +300,13 @@
 	
 	/* Check if the node is not already open */
-	unsigned long key[] = {
-		[OPEN_NODES_DEV_HANDLE_KEY] = inst->service_id,
-		[OPEN_NODES_INODE_KEY] = index
+	node_key_t key = {
+		.service_id = inst->service_id,
+		.index = index
 	};
 	
-	link_t *already_open = hash_table_find(&open_nodes, key);
+	ht_link_t *already_open = hash_table_find(&open_nodes, &key);
 	ext4fs_node_t *enode = NULL;
 	if (already_open) {
-		enode = hash_table_get_instance(already_open, ext4fs_node_t, link);
+		enode = hash_table_get_inst(already_open, ext4fs_node_t, link);
 		*rfn = enode->fs_node;
 		enode->references++;
@@ -364,10 +349,9 @@
 	enode->references = 1;
 	enode->fs_node = fs_node;
-	link_initialize(&enode->link);
 	
 	fs_node->data = enode;
 	*rfn = fs_node;
 	
-	hash_table_insert(&open_nodes, key, &enode->link);
+	hash_table_insert(&open_nodes, &enode->link);
 	inst->open_nodes_count++;
 	
@@ -386,10 +370,5 @@
 int ext4fs_node_put_core(ext4fs_node_t *enode)
 {
-	unsigned long key[] = {
-		[OPEN_NODES_DEV_HANDLE_KEY] = enode->instance->service_id,
-		[OPEN_NODES_INODE_KEY] = enode->inode_ref->index
-	};
-	
-	hash_table_remove(&open_nodes, key, OPEN_NODES_KEYS);
+	hash_table_remove_item(&open_nodes, &enode->link);
 	assert(enode->instance->open_nodes_count > 0);
 	enode->instance->open_nodes_count--;
@@ -498,13 +477,6 @@
 	enode->references = 1;
 	
-	link_initialize(&enode->link);
-	
-	unsigned long key[] = {
-		[OPEN_NODES_DEV_HANDLE_KEY] = inst->service_id,
-		[OPEN_NODES_INODE_KEY] = inode_ref->index
-	};
-	
 	fibril_mutex_lock(&open_nodes_lock);
-	hash_table_insert(&open_nodes, key, &enode->link);
+	hash_table_insert(&open_nodes, &enode->link);
 	fibril_mutex_unlock(&open_nodes_lock);
 	inst->open_nodes_count++;
Index: uspace/srv/fs/fat/fat.h
===================================================================
--- uspace/srv/fs/fat/fat.h	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/srv/fs/fat/fat.h	(revision 062d9000625057300f609429080872d6492b542e)
@@ -190,7 +190,7 @@
 typedef struct {
 	/** Used indices (position) hash table link. */
-	link_t		uph_link;
+	ht_link_t		uph_link;
 	/** Used indices (index) hash table link. */
-	link_t		uih_link;
+	ht_link_t		uih_link;
 
 	fibril_mutex_t	lock;
Index: uspace/srv/fs/fat/fat_idx.c
===================================================================
--- uspace/srv/fs/fat/fat_idx.c	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/srv/fs/fat/fat_idx.c	(revision 062d9000625057300f609429080872d6492b542e)
@@ -41,4 +41,5 @@
 #include <str.h>
 #include <adt/hash_table.h>
+#include <adt/hash.h>
 #include <adt/list.h>
 #include <assert.h>
@@ -58,6 +59,6 @@
  */
 typedef struct {
-	link_t		link;
-	service_id_t	service_id;
+	link_t link;
+	service_id_t service_id;
 
 	/** Next unassigned index. */
@@ -97,5 +98,5 @@
 			return u;
 	}
-	
+
 	if (lock)
 		fibril_mutex_unlock(&unused_lock);
@@ -113,70 +114,48 @@
 static hash_table_t up_hash;
 
-#define UPH_BUCKETS_LOG	12
-#define UPH_BUCKETS	(1 << UPH_BUCKETS_LOG)
-
-#define UPH_SID_KEY	0
-#define UPH_PFC_KEY	1
-#define UPH_PDI_KEY	2
-
-static hash_index_t pos_hash(unsigned long key[])
-{
-	service_id_t service_id = (service_id_t)key[UPH_SID_KEY];
-	fat_cluster_t pfc = (fat_cluster_t)key[UPH_PFC_KEY];
-	unsigned pdi = (unsigned)key[UPH_PDI_KEY];
-
-	hash_index_t h;
-
-	/*
-	 * The least significant half of all bits are the least significant bits
-	 * of the parent node's first cluster.
-	 *
-	 * The least significant half of the most significant half of all bits
-	 * are the least significant bits of the node's dentry index within the
-	 * parent directory node.
-	 *
-	 * The most significant half of the most significant half of all bits
-	 * are the least significant bits of the device handle.
-	 */
-	h = pfc & ((1 << (UPH_BUCKETS_LOG / 2)) - 1);
-	h |= (pdi & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) <<
-	    (UPH_BUCKETS_LOG / 2); 
-	h |= (service_id & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) <<
-	    (3 * (UPH_BUCKETS_LOG / 4));
-
-	return h;
-}
-
-static int pos_compare(unsigned long key[], hash_count_t keys, link_t *item)
-{
-	service_id_t service_id = (service_id_t)key[UPH_SID_KEY];
+typedef struct {
+	service_id_t service_id;
 	fat_cluster_t pfc;
 	unsigned pdi;
-	fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uph_link);
-
-	switch (keys) {
-	case 1:
-		return (service_id == fidx->service_id);
-	case 3:
-		pfc = (fat_cluster_t) key[UPH_PFC_KEY];
-		pdi = (unsigned) key[UPH_PDI_KEY];
-		return (service_id == fidx->service_id) && (pfc == fidx->pfc) &&
-		    (pdi == fidx->pdi);
-	default:
-		assert((keys == 1) || (keys == 3));
-	}
-
-	return 0;
-}
-
-static void pos_remove_callback(link_t *item)
-{
-	/* nothing to do */
-}
-
-static hash_table_operations_t uph_ops = {
+} pos_key_t;
+
+static inline size_t pos_key_hash(void *key)
+{
+	pos_key_t *pos = (pos_key_t*)key;
+	
+	size_t hash = 0;
+	hash = hash_combine(pos->pfc, pos->pdi);
+	return hash_combine(hash, pos->service_id);
+}
+
+static size_t pos_hash(const ht_link_t *item)
+{
+	fat_idx_t *fidx = hash_table_get_inst(item, fat_idx_t, uph_link);
+	
+	pos_key_t pkey = {
+		.service_id = fidx->service_id,
+		.pfc = fidx->pfc,
+		.pdi = fidx->pdi,
+	};
+	
+	return pos_key_hash(&pkey);
+}
+
+static bool pos_key_equal(void *key, const ht_link_t *item)
+{
+	pos_key_t *pos = (pos_key_t*)key;
+	fat_idx_t *fidx = hash_table_get_inst(item, fat_idx_t, uph_link);
+	
+	return pos->service_id == fidx->service_id
+		&& pos->pdi == fidx->pdi
+		&& pos->pfc == fidx->pfc;
+}
+
+static hash_table_ops_t uph_ops = {
 	.hash = pos_hash,
-	.compare = pos_compare,
-	.remove_callback = pos_remove_callback,
+	.key_hash = pos_key_hash,
+	.key_equal = pos_key_equal,
+	.equal = 0,
+	.remove_callback = 0,
 };
 
@@ -187,54 +166,41 @@
 static hash_table_t ui_hash;
 
-#define UIH_BUCKETS_LOG	12
-#define UIH_BUCKETS	(1 << UIH_BUCKETS_LOG)
-
-#define UIH_SID_KEY	0
-#define UIH_INDEX_KEY	1
-
-static hash_index_t idx_hash(unsigned long key[])
-{
-	service_id_t service_id = (service_id_t)key[UIH_SID_KEY];
-	fs_index_t index = (fs_index_t)key[UIH_INDEX_KEY];
-
-	hash_index_t h;
-
-	h = service_id & ((1 << (UIH_BUCKETS_LOG / 2)) - 1);
-	h |= (index & ((1 << (UIH_BUCKETS_LOG / 2)) - 1)) <<
-	    (UIH_BUCKETS_LOG / 2);
-
-	return h;
-}
-
-static int idx_compare(unsigned long key[], hash_count_t keys, link_t *item)
-{
-	service_id_t service_id = (service_id_t)key[UIH_SID_KEY];
+typedef struct {
+	service_id_t service_id;
 	fs_index_t index;
-	fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uih_link);
-
-	switch (keys) {
-	case 1:
-		return (service_id == fidx->service_id);
-	case 2:
-		index = (fs_index_t) key[UIH_INDEX_KEY];
-		return (service_id == fidx->service_id) &&
-		    (index == fidx->index);
-	default:
-		assert((keys == 1) || (keys == 2));
-	}
-
-	return 0;
-}
-
-static void idx_remove_callback(link_t *item)
-{
-	fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uih_link);
+} idx_key_t;
+
+static size_t idx_key_hash(void *key_arg)
+{
+	idx_key_t *key = (idx_key_t*)key_arg;
+	return hash_combine(key->service_id, key->index);
+}
+
+static size_t idx_hash(const ht_link_t *item)
+{
+	fat_idx_t *fidx = hash_table_get_inst(item, fat_idx_t, uih_link);
+	return hash_combine(fidx->service_id, fidx->index);
+}
+
+static bool idx_key_equal(void *key_arg, const ht_link_t *item)
+{
+	fat_idx_t *fidx = hash_table_get_inst(item, fat_idx_t, uih_link);
+	idx_key_t *key = (idx_key_t*)key_arg;
+	
+	return key->index == fidx->index && key->service_id == fidx->service_id;
+}
+
+static void idx_remove_callback(ht_link_t *item)
+{
+	fat_idx_t *fidx = hash_table_get_inst(item, fat_idx_t, uih_link);
 
 	free(fidx);
 }
 
-static hash_table_operations_t uih_ops = {
+static hash_table_ops_t uih_ops = {
 	.hash = idx_hash,
-	.compare = idx_compare,
+	.key_hash = idx_key_hash,
+	.key_equal = idx_key_equal,
+	.equal = 0,
 	.remove_callback = idx_remove_callback,
 };
@@ -377,6 +343,4 @@
 	}
 		
-	link_initialize(&fidx->uph_link);
-	link_initialize(&fidx->uih_link);
 	fibril_mutex_initialize(&fidx->lock);
 	fidx->service_id = service_id;
@@ -401,10 +365,5 @@
 	}
 		
-	unsigned long ikey[] = {
-		[UIH_SID_KEY] = service_id,
-		[UIH_INDEX_KEY] = fidx->index,
-	};
-	
-	hash_table_insert(&ui_hash, ikey, &fidx->uih_link);
+	hash_table_insert(&ui_hash, &fidx->uih_link);
 	fibril_mutex_lock(&fidx->lock);
 	fibril_mutex_unlock(&used_lock);
@@ -418,15 +377,15 @@
 {
 	fat_idx_t *fidx;
-	link_t *l;
-	unsigned long pkey[] = {
-		[UPH_SID_KEY] = service_id,
-		[UPH_PFC_KEY] = pfc,
-		[UPH_PDI_KEY] = pdi,
+
+	pos_key_t pos_key = {
+		.service_id = service_id,
+		.pfc = pfc,
+		.pdi = pdi,
 	};
 
 	fibril_mutex_lock(&used_lock);
-	l = hash_table_find(&up_hash, pkey);
+	ht_link_t *l = hash_table_find(&up_hash, &pos_key);
 	if (l) {
-		fidx = hash_table_get_instance(l, fat_idx_t, uph_link);
+		fidx = hash_table_get_inst(l, fat_idx_t, uph_link);
 	} else {
 		int rc;
@@ -438,14 +397,9 @@
 		}
 		
-		unsigned long ikey[] = {
-			[UIH_SID_KEY] = service_id,
-			[UIH_INDEX_KEY] = fidx->index,
-		};
-	
 		fidx->pfc = pfc;
 		fidx->pdi = pdi;
 
-		hash_table_insert(&up_hash, pkey, &fidx->uph_link);
-		hash_table_insert(&ui_hash, ikey, &fidx->uih_link);
+		hash_table_insert(&up_hash, &fidx->uph_link);
+		hash_table_insert(&ui_hash, &fidx->uih_link);
 	}
 	fibril_mutex_lock(&fidx->lock);
@@ -457,12 +411,6 @@
 void fat_idx_hashin(fat_idx_t *idx)
 {
-	unsigned long pkey[] = {
-		[UPH_SID_KEY] = idx->service_id,
-		[UPH_PFC_KEY] = idx->pfc,
-		[UPH_PDI_KEY] = idx->pdi,
-	};
-
-	fibril_mutex_lock(&used_lock);
-	hash_table_insert(&up_hash, pkey, &idx->uph_link);
+	fibril_mutex_lock(&used_lock);
+	hash_table_insert(&up_hash, &idx->uph_link);
 	fibril_mutex_unlock(&used_lock);
 }
@@ -470,12 +418,6 @@
 void fat_idx_hashout(fat_idx_t *idx)
 {
-	unsigned long pkey[] = {
-		[UPH_SID_KEY] = idx->service_id,
-		[UPH_PFC_KEY] = idx->pfc,
-		[UPH_PDI_KEY] = idx->pdi,
-	};
-
-	fibril_mutex_lock(&used_lock);
-	hash_table_remove(&up_hash, pkey, 3);
+	fibril_mutex_lock(&used_lock);
+	hash_table_remove_item(&up_hash, &idx->uph_link);
 	fibril_mutex_unlock(&used_lock);
 }
@@ -485,14 +427,14 @@
 {
 	fat_idx_t *fidx = NULL;
-	link_t *l;
-	unsigned long ikey[] = {
-		[UIH_SID_KEY] = service_id,
-		[UIH_INDEX_KEY] = index,
+
+	idx_key_t idx_key = {
+		.service_id = service_id,
+		.index = index,
 	};
 
 	fibril_mutex_lock(&used_lock);
-	l = hash_table_find(&ui_hash, ikey);
+	ht_link_t *l = hash_table_find(&ui_hash, &idx_key);
 	if (l) {
-		fidx = hash_table_get_instance(l, fat_idx_t, uih_link);
+		fidx = hash_table_get_inst(l, fat_idx_t, uih_link);
 		fibril_mutex_lock(&fidx->lock);
 	}
@@ -508,10 +450,8 @@
 void fat_idx_destroy(fat_idx_t *idx)
 {
-	unsigned long ikey[] = {
-		[UIH_SID_KEY] = idx->service_id,
-		[UIH_INDEX_KEY] = idx->index,
+	idx_key_t idx_key = {
+		.service_id = idx->service_id,
+		.index = idx->index,
 	};
-	service_id_t service_id = idx->service_id;
-	fs_index_t index = idx->index;
 
 	assert(idx->pfc == FAT_CLST_RES0);
@@ -523,8 +463,8 @@
 	 * the index hash only.
 	 */
-	hash_table_remove(&ui_hash, ikey, 2);
+	hash_table_remove(&ui_hash, &idx_key);
 	fibril_mutex_unlock(&used_lock);
 	/* Release the VFS index. */
-	fat_index_free(service_id, index);
+	fat_index_free(idx_key.service_id, idx_key.index);
 	/* The index structure itself is freed in idx_remove_callback(). */
 }
@@ -532,7 +472,7 @@
 int fat_idx_init(void)
 {
-	if (!hash_table_create(&up_hash, UPH_BUCKETS, 3, &uph_ops)) 
+	if (!hash_table_create(&up_hash, 0, 0, &uph_ops)) 
 		return ENOMEM;
-	if (!hash_table_create(&ui_hash, UIH_BUCKETS, 2, &uih_ops)) {
+	if (!hash_table_create(&ui_hash, 0, 0, &uih_ops)) {
 		hash_table_destroy(&up_hash);
 		return ENOMEM;
@@ -544,4 +484,5 @@
 {
 	/* We assume the hash tables are empty. */
+	assert(hash_table_empty(&up_hash) && hash_table_empty(&ui_hash));
 	hash_table_destroy(&up_hash);
 	hash_table_destroy(&ui_hash);
@@ -568,13 +509,30 @@
 }
 
+static bool rm_pos_service_id(ht_link_t *item, void *arg)
+{
+	service_id_t service_id = *(service_id_t*)arg;
+	fat_idx_t *fidx = hash_table_get_inst(item, fat_idx_t, uph_link);
+
+	if (fidx->service_id == service_id) {
+		hash_table_remove_item(&up_hash, item);
+	}
+	
+	return true;
+}
+
+static bool rm_idx_service_id(ht_link_t *item, void *arg)
+{
+	service_id_t service_id = *(service_id_t*)arg;
+	fat_idx_t *fidx = hash_table_get_inst(item, fat_idx_t, uih_link);
+
+	if (fidx->service_id == service_id) {
+		hash_table_remove_item(&ui_hash, item);
+	}
+	
+	return true;
+}
+
 void fat_idx_fini_by_service_id(service_id_t service_id)
 {
-	unsigned long ikey[] = {
-		[UIH_SID_KEY] = service_id
-	};
-	unsigned long pkey[] = {
-		[UPH_SID_KEY] = service_id
-	};
-
 	/*
 	 * Remove this instance's index structure from up_hash and ui_hash.
@@ -583,6 +541,6 @@
 	 */
 	fibril_mutex_lock(&used_lock);
-	hash_table_remove(&up_hash, pkey, 1);
-	hash_table_remove(&ui_hash, ikey, 1);
+	hash_table_apply(&up_hash, rm_pos_service_id, &service_id);
+	hash_table_apply(&ui_hash, rm_idx_service_id, &service_id);
 	fibril_mutex_unlock(&used_lock);
 
Index: uspace/srv/fs/locfs/locfs_ops.c
===================================================================
--- uspace/srv/fs/locfs/locfs_ops.c	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/srv/fs/locfs/locfs_ops.c	(revision 062d9000625057300f609429080872d6492b542e)
@@ -61,5 +61,5 @@
 	async_sess_t *sess;       /**< If NULL, the structure is incomplete. */
 	size_t refcount;
-	link_t link;
+	ht_link_t link;
 	fibril_condvar_t cv;      /**< Broadcast when completed. */
 } service_t;
@@ -71,28 +71,33 @@
 static FIBRIL_MUTEX_INITIALIZE(services_mutex);
 
-#define SERVICES_KEYS        1
-#define SERVICES_KEY_HANDLE  0
-#define SERVICES_BUCKETS     256
-
 /* Implementation of hash table interface for the nodes hash table. */
-static hash_index_t services_hash(unsigned long key[])
-{
-	return key[SERVICES_KEY_HANDLE] % SERVICES_BUCKETS;
-}
-
-static int services_compare(unsigned long key[], hash_count_t keys, link_t *item)
-{
-	service_t *dev = hash_table_get_instance(item, service_t, link);
-	return (dev->service_id == (service_id_t) key[SERVICES_KEY_HANDLE]);
-}
-
-static void services_remove_callback(link_t *item)
-{
-	free(hash_table_get_instance(item, service_t, link));
-}
-
-static hash_table_operations_t services_ops = {
+
+static size_t services_key_hash(void *key)
+{
+	return *(service_id_t*)key;
+}
+
+static size_t services_hash(const ht_link_t *item)
+{
+	service_t *dev = hash_table_get_inst(item, service_t, link);
+	return dev->service_id;
+}
+
+static bool services_key_equal(void *key, const ht_link_t *item)
+{
+	service_t *dev = hash_table_get_inst(item, service_t, link);
+	return (dev->service_id == *(service_id_t*)key);
+}
+
+static void services_remove_callback(ht_link_t *item)
+{
+	free(hash_table_get_inst(item, service_t, link));
+}
+
+static hash_table_ops_t services_ops = {
 	.hash = services_hash,
-	.compare = services_compare,
+	.key_hash = services_key_hash,
+	.key_equal = services_key_equal,
+	.equal = 0, 
 	.remove_callback = services_remove_callback
 };
@@ -229,12 +234,8 @@
 		/* Device node */
 		
-		unsigned long key[] = {
-			[SERVICES_KEY_HANDLE] = (unsigned long) node->service_id
-		};
-		link_t *lnk;
-		
 		fibril_mutex_lock(&services_mutex);
+		ht_link_t *lnk;
 restart:
-		lnk = hash_table_find(&services, key);
+		lnk = hash_table_find(&services, &node->service_id);
 		if (lnk == NULL) {
 			service_t *dev = (service_t *) malloc(sizeof(service_t));
@@ -256,5 +257,5 @@
 			 * below.
 			 */
-			hash_table_insert(&services, key, &dev->link);
+			hash_table_insert(&services, &dev->link);
 			
 			/*
@@ -279,5 +280,5 @@
 				 * entry and free the device structure.
 				 */
-				hash_table_remove(&services, key, SERVICES_KEYS);
+				hash_table_remove(&services, &node->service_id);
 				fibril_mutex_unlock(&services_mutex);
 				
@@ -288,5 +289,5 @@
 			dev->sess = sess;
 		} else {
-			service_t *dev = hash_table_get_instance(lnk, service_t, link);
+			service_t *dev = hash_table_get_inst(lnk, service_t, link);
 			
 			if (!dev->sess) {
@@ -450,6 +451,5 @@
 bool locfs_init(void)
 {
-	if (!hash_table_create(&services, SERVICES_BUCKETS,
-	    SERVICES_KEYS, &services_ops))
+	if (!hash_table_create(&services, 0,  0, &services_ops))
 		return false;
 	
@@ -555,10 +555,7 @@
 		/* Device node */
 		
-		unsigned long key[] = {
-			[SERVICES_KEY_HANDLE] = (unsigned long) index
-		};
-		
 		fibril_mutex_lock(&services_mutex);
-		link_t *lnk = hash_table_find(&services, key);
+		service_id_t service_index = index;
+		ht_link_t *lnk = hash_table_find(&services, &service_index);
 		if (lnk == NULL) {
 			fibril_mutex_unlock(&services_mutex);
@@ -566,5 +563,5 @@
 		}
 		
-		service_t *dev = hash_table_get_instance(lnk, service_t, link);
+		service_t *dev = hash_table_get_inst(lnk, service_t, link);
 		assert(dev->sess);
 		
@@ -621,10 +618,8 @@
 	if (type == LOC_OBJECT_SERVICE) {
 		/* Device node */
-		unsigned long key[] = {
-			[SERVICES_KEY_HANDLE] = (unsigned long) index
-		};
 		
 		fibril_mutex_lock(&services_mutex);
-		link_t *lnk = hash_table_find(&services, key);
+		service_id_t service_index = index;
+		ht_link_t *lnk = hash_table_find(&services, &service_index);
 		if (lnk == NULL) {
 			fibril_mutex_unlock(&services_mutex);
@@ -632,5 +627,5 @@
 		}
 		
-		service_t *dev = hash_table_get_instance(lnk, service_t, link);
+		service_t *dev = hash_table_get_inst(lnk, service_t, link);
 		assert(dev->sess);
 		
@@ -691,10 +686,8 @@
 	
 	if (type == LOC_OBJECT_SERVICE) {
-		unsigned long key[] = {
-			[SERVICES_KEY_HANDLE] = (unsigned long) index
-		};
 		
 		fibril_mutex_lock(&services_mutex);
-		link_t *lnk = hash_table_find(&services, key);
+		service_id_t service_index = index;
+		ht_link_t *lnk = hash_table_find(&services, &service_index);
 		if (lnk == NULL) {
 			fibril_mutex_unlock(&services_mutex);
@@ -702,5 +695,5 @@
 		}
 		
-		service_t *dev = hash_table_get_instance(lnk, service_t, link);
+		service_t *dev = hash_table_get_inst(lnk, service_t, link);
 		assert(dev->sess);
 		dev->refcount--;
@@ -708,5 +701,6 @@
 		if (dev->refcount == 0) {
 			async_hangup(dev->sess);
-			hash_table_remove(&services, key, SERVICES_KEYS);
+			service_id_t service_index = index;
+			hash_table_remove(&services, &service_index);
 		}
 		
@@ -732,10 +726,8 @@
 	
 	if (type == LOC_OBJECT_SERVICE) {
-		unsigned long key[] = {
-			[SERVICES_KEY_HANDLE] = (unsigned long) index
-		};
-		
+
 		fibril_mutex_lock(&services_mutex);
-		link_t *lnk = hash_table_find(&services, key);
+		service_id_t service_index = index;
+		ht_link_t *lnk = hash_table_find(&services, &service_index);
 		if (lnk == NULL) {
 			fibril_mutex_unlock(&services_mutex);
@@ -743,5 +735,5 @@
 		}
 		
-		service_t *dev = hash_table_get_instance(lnk, service_t, link);
+		service_t *dev = hash_table_get_inst(lnk, service_t, link);
 		assert(dev->sess);
 		
Index: uspace/srv/fs/mfs/mfs.h
===================================================================
--- uspace/srv/fs/mfs/mfs.h	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/srv/fs/mfs/mfs.h	(revision 062d9000625057300f609429080872d6492b542e)
@@ -142,5 +142,5 @@
 	unsigned refcnt;
 	fs_node_t *fsnode;
-	link_t link;
+	ht_link_t link;
 };
 
Index: uspace/srv/fs/mfs/mfs_ops.c
===================================================================
--- uspace/srv/fs/mfs/mfs_ops.c	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/srv/fs/mfs/mfs_ops.c	(revision 062d9000625057300f609429080872d6492b542e)
@@ -35,10 +35,7 @@
 #include <align.h>
 #include <adt/hash_table.h>
+#include <adt/hash.h>
 #include "mfs.h"
 
-#define OPEN_NODES_KEYS 2
-#define OPEN_NODES_SERVICE_KEY 0
-#define OPEN_NODES_INODE_KEY 1
-#define OPEN_NODES_BUCKETS 256
 
 static bool check_magic_number(uint16_t magic, bool *native,
@@ -61,8 +58,4 @@
 static int mfs_unlink(fs_node_t *, fs_node_t *, const char *name);
 static int mfs_destroy_node(fs_node_t *fn);
-static hash_index_t open_nodes_hash(unsigned long key[]);
-static int open_nodes_compare(unsigned long key[], hash_count_t keys,
-    link_t *item);
-static void open_nodes_remove_cb(link_t *link);
 static int mfs_node_get(fs_node_t **rfn, service_id_t service_id,
     fs_index_t index);
@@ -95,38 +88,40 @@
 
 /* Hash table interface for open nodes hash table */
-static hash_index_t
-open_nodes_hash(unsigned long key[])
-{
-	/* TODO: This is very simple and probably can be improved */
-	return key[OPEN_NODES_INODE_KEY] % OPEN_NODES_BUCKETS;
-}
-
-static int
-open_nodes_compare(unsigned long key[], hash_count_t keys,
-    link_t *item)
-{
-	struct mfs_node *mnode = hash_table_get_instance(item, struct mfs_node, link);
-	assert(keys > 0);
-	if (mnode->instance->service_id !=
-	    ((service_id_t) key[OPEN_NODES_SERVICE_KEY])) {
-		return false;
-	}
-	if (keys == 1) {
-		return true;
-	}
-	assert(keys == 2);
-	return (mnode->ino_i->index == key[OPEN_NODES_INODE_KEY]);
-}
-
-static void
-open_nodes_remove_cb(link_t *link)
-{
-	/* We don't use remove callback for this hash table */
-}
-
-static hash_table_operations_t open_nodes_ops = {
+
+typedef struct {
+	service_id_t service_id;
+	fs_index_t index;
+} node_key_t;
+
+static size_t
+open_nodes_key_hash(void *key)
+{
+	node_key_t *node_key = (node_key_t*)key;
+	return hash_combine(node_key->service_id, node_key->index);
+}
+
+static size_t
+open_nodes_hash(const ht_link_t *item)
+{
+	struct mfs_node *m = hash_table_get_inst(item, struct mfs_node, link);
+	return hash_combine(m->instance->service_id, m->ino_i->index);
+}
+
+static bool
+open_nodes_key_equal(void *key, const ht_link_t *item)
+{
+	node_key_t *node_key = (node_key_t*)key;
+	struct mfs_node *mnode = hash_table_get_inst(item, struct mfs_node, link);
+
+	return node_key->service_id == mnode->instance->service_id
+		&& node_key->index == mnode->ino_i->index;
+}
+
+static hash_table_ops_t open_nodes_ops = {
 	.hash = open_nodes_hash,
-	.compare = open_nodes_compare,
-	.remove_callback = open_nodes_remove_cb,
+	.key_hash = open_nodes_key_hash,
+	.key_equal = open_nodes_key_equal,
+	.equal = 0,
+	.remove_callback = 0,
 };
 
@@ -134,6 +129,5 @@
 mfs_global_init(void)
 {
-	if (!hash_table_create(&open_nodes, OPEN_NODES_BUCKETS,
-	    OPEN_NODES_KEYS, &open_nodes_ops)) {
+	if (!hash_table_create(&open_nodes, 0, 0, &open_nodes_ops)) {
 		return ENOMEM;
 	}
@@ -406,13 +400,6 @@
 	mnode->refcnt = 1;
 
-	link_initialize(&mnode->link);
-
-	unsigned long key[] = {
-		[OPEN_NODES_SERVICE_KEY] = inst->service_id,
-		[OPEN_NODES_INODE_KEY] = inum,
-	};
-
 	fibril_mutex_lock(&open_nodes_lock);
-	hash_table_insert(&open_nodes, key, &mnode->link);
+	hash_table_insert(&open_nodes, &mnode->link);
 	fibril_mutex_unlock(&open_nodes_lock);
 	inst->open_nodes_cnt++;
@@ -513,9 +500,5 @@
 	mnode->refcnt--;
 	if (mnode->refcnt == 0) {
-		unsigned long key[] = {
-			[OPEN_NODES_SERVICE_KEY] = mnode->instance->service_id,
-			[OPEN_NODES_INODE_KEY] = mnode->ino_i->index
-		};
-		hash_table_remove(&open_nodes, key, OPEN_NODES_KEYS);
+		hash_table_remove_item(&open_nodes, &mnode->link);
 		assert(mnode->instance->open_nodes_cnt > 0);
 		mnode->instance->open_nodes_cnt--;
@@ -576,12 +559,13 @@
 
 	/* Check if the node is not already open */
-	unsigned long key[] = {
-		[OPEN_NODES_SERVICE_KEY] = inst->service_id,
-		[OPEN_NODES_INODE_KEY] = index,
+	node_key_t key = {
+		.service_id = inst->service_id,
+		.index = index
 	};
-	link_t *already_open = hash_table_find(&open_nodes, key);
+	
+	ht_link_t *already_open = hash_table_find(&open_nodes, &key);
 
 	if (already_open) {
-		mnode = hash_table_get_instance(already_open, struct mfs_node, link);
+		mnode = hash_table_get_inst(already_open, struct mfs_node, link);
 		*rfn = mnode->fsnode;
 		mnode->refcnt++;
@@ -614,5 +598,4 @@
 	mnode->ino_i = ino_i;
 	mnode->refcnt = 1;
-	link_initialize(&mnode->link);
 
 	mnode->instance = inst;
@@ -621,5 +604,5 @@
 	*rfn = node;
 
-	hash_table_insert(&open_nodes, key, &mnode->link);
+	hash_table_insert(&open_nodes, &mnode->link);
 	inst->open_nodes_cnt++;
 
Index: uspace/srv/fs/tmpfs/tmpfs.h
===================================================================
--- uspace/srv/fs/tmpfs/tmpfs.h	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/srv/fs/tmpfs/tmpfs.h	(revision 062d9000625057300f609429080872d6492b542e)
@@ -62,5 +62,5 @@
 	fs_index_t index;	/**< TMPFS node index. */
 	service_id_t service_id;/**< Service ID of block device. */
-	link_t nh_link;		/**< Nodes hash table link. */
+	ht_link_t nh_link;		/**< Nodes hash table link. */
 	tmpfs_dentry_type_t type;
 	unsigned lnkcnt;	/**< Link count. */
Index: uspace/srv/fs/tmpfs/tmpfs_ops.c
===================================================================
--- uspace/srv/fs/tmpfs/tmpfs_ops.c	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/srv/fs/tmpfs/tmpfs_ops.c	(revision 062d9000625057300f609429080872d6492b542e)
@@ -50,4 +50,5 @@
 #include <sys/types.h>
 #include <adt/hash_table.h>
+#include <adt/hash.h>
 #include <as.h>
 #include <libfs.h>
@@ -55,6 +56,4 @@
 #define min(a, b)		((a) < (b) ? (a) : (b))
 #define max(a, b)		((a) > (b) ? (a) : (b))
-
-#define NODES_BUCKETS	256
 
 /** All root nodes have index 0. */
@@ -142,35 +141,36 @@
 hash_table_t nodes;
 
-#define NODES_KEY_DEV	0	
-#define NODES_KEY_INDEX	1
-
-/* Implementation of hash table interface for the nodes hash table. */
-static hash_index_t nodes_hash(unsigned long key[])
-{
-	return key[NODES_KEY_INDEX] % NODES_BUCKETS;
-}
-
-static int nodes_compare(unsigned long key[], hash_count_t keys, link_t *item)
-{
-	tmpfs_node_t *nodep = hash_table_get_instance(item, tmpfs_node_t,
-	    nh_link);
-	
-	switch (keys) {
-	case 1:
-		return (nodep->service_id == key[NODES_KEY_DEV]);
-	case 2:	
-		return ((nodep->service_id == key[NODES_KEY_DEV]) &&
-		    (nodep->index == key[NODES_KEY_INDEX]));
-	default:
-		assert((keys == 1) || (keys == 2));
-	}
-
-	return 0;
-}
-
-static void nodes_remove_callback(link_t *item)
-{
-	tmpfs_node_t *nodep = hash_table_get_instance(item, tmpfs_node_t,
-	    nh_link);
+/* 
+ * Implementation of hash table interface for the nodes hash table. 
+ */
+
+typedef struct {
+	service_id_t service_id;
+	fs_index_t index;
+} node_key_t;
+
+static size_t nodes_key_hash(void *k)
+{
+	node_key_t *key = (node_key_t *)k;
+	return hash_combine(key->service_id, key->index);
+}
+
+static size_t nodes_hash(const ht_link_t *item)
+{
+	tmpfs_node_t *nodep = hash_table_get_inst(item, tmpfs_node_t, nh_link);
+	return hash_combine(nodep->service_id, nodep->index);
+}
+
+static bool nodes_key_equal(void *key_arg, const ht_link_t *item)
+{
+	tmpfs_node_t *node = hash_table_get_inst(item, tmpfs_node_t, nh_link);
+	node_key_t *key = (node_key_t *)key_arg;
+	
+	return key->service_id == node->service_id && key->index == node->index;
+}
+
+static void nodes_remove_callback(ht_link_t *item)
+{
+	tmpfs_node_t *nodep = hash_table_get_inst(item, tmpfs_node_t, nh_link);
 
 	while (!list_empty(&nodep->cs_list)) {
@@ -192,7 +192,9 @@
 
 /** TMPFS nodes hash table operations. */
-hash_table_operations_t nodes_ops = {
+hash_table_ops_t nodes_ops = {
 	.hash = nodes_hash,
-	.compare = nodes_compare,
+	.key_hash = nodes_key_hash,
+	.key_equal = nodes_key_equal,
+	.equal = 0,
 	.remove_callback = nodes_remove_callback
 };
@@ -207,5 +209,4 @@
 	nodep->size = 0;
 	nodep->data = NULL;
-	link_initialize(&nodep->nh_link);
 	list_initialize(&nodep->cs_list);
 }
@@ -220,5 +221,5 @@
 bool tmpfs_init(void)
 {
-	if (!hash_table_create(&nodes, NODES_BUCKETS, 2, &nodes_ops))
+	if (!hash_table_create(&nodes, 0, 0, &nodes_ops))
 		return false;
 	
@@ -238,17 +239,18 @@
 }
 
+static bool rm_service_id_nodes(ht_link_t *item, void *arg)
+{
+	service_id_t sid = *(service_id_t*)arg;
+	tmpfs_node_t *node = hash_table_get_inst(item, tmpfs_node_t, nh_link);
+	
+	if (node->service_id == sid) {
+		hash_table_remove_item(&nodes, &node->nh_link);
+	}
+	return true;
+}
+
 static void tmpfs_instance_done(service_id_t service_id)
-{
-	unsigned long key[] = {
-		[NODES_KEY_DEV] = service_id
-	};
-	/*
-	 * Here we are making use of one special feature of our hash table
-	 * implementation, which allows to remove more items based on a partial
-	 * key match. In the following, we are going to remove all nodes
-	 * matching our device handle. The nodes_remove_callback() function will
-	 * take care of resource deallocation.
-	 */
-	hash_table_remove(&nodes, key, 1);
+{	
+	hash_table_apply(&nodes, rm_service_id_nodes, &service_id);
 }
 
@@ -272,12 +274,14 @@
 int tmpfs_node_get(fs_node_t **rfn, service_id_t service_id, fs_index_t index)
 {
-	unsigned long key[] = {
-		[NODES_KEY_DEV] = service_id,
-		[NODES_KEY_INDEX] = index
+	node_key_t key = {
+		.service_id = service_id,
+		.index = index
 	};
-	link_t *lnk = hash_table_find(&nodes, key);
+	
+	ht_link_t *lnk = hash_table_find(&nodes, &key);
+	
 	if (lnk) {
 		tmpfs_node_t *nodep;
-		nodep = hash_table_get_instance(lnk, tmpfs_node_t, nh_link);
+		nodep = hash_table_get_inst(lnk, tmpfs_node_t, nh_link);
 		*rfn = FS_NODE(nodep);
 	} else {
@@ -331,9 +335,5 @@
 
 	/* Insert the new node into the nodes hash table. */
-	unsigned long key[] = {
-		[NODES_KEY_DEV] = nodep->service_id,
-		[NODES_KEY_INDEX] = nodep->index
-	};
-	hash_table_insert(&nodes, key, &nodep->nh_link);
+	hash_table_insert(&nodes, &nodep->nh_link);
 	*rfn = FS_NODE(nodep);
 	return EOK;
@@ -346,10 +346,6 @@
 	assert(!nodep->lnkcnt);
 	assert(list_empty(&nodep->cs_list));
-
-	unsigned long key[] = {
-		[NODES_KEY_DEV] = nodep->service_id,
-		[NODES_KEY_INDEX] = nodep->index
-	};
-	hash_table_remove(&nodes, key, 2);
+	
+	hash_table_remove_item(&nodes, &nodep->nh_link);
 
 	/*
@@ -476,14 +472,14 @@
 	 * Lookup the respective TMPFS node.
 	 */
-	link_t *hlp;
-	unsigned long key[] = {
-		[NODES_KEY_DEV] = service_id,
-		[NODES_KEY_INDEX] = index
+	node_key_t key = {
+		.service_id = service_id,
+		.index = index
 	};
-	hlp = hash_table_find(&nodes, key);
+	
+	ht_link_t *hlp = hash_table_find(&nodes, &key);
 	if (!hlp)
 		return ENOENT;
-	tmpfs_node_t *nodep = hash_table_get_instance(hlp, tmpfs_node_t,
-	    nh_link);
+	
+	tmpfs_node_t *nodep = hash_table_get_inst(hlp, tmpfs_node_t, nh_link);
 	
 	/*
@@ -538,14 +534,15 @@
 	 * Lookup the respective TMPFS node.
 	 */
-	link_t *hlp;
-	unsigned long key[] = {
-		[NODES_KEY_DEV] = service_id,
-		[NODES_KEY_INDEX] = index
+	node_key_t key = {
+		.service_id = service_id,
+		.index = index
 	};
-	hlp = hash_table_find(&nodes, key);
+	
+	ht_link_t *hlp = hash_table_find(&nodes, &key);
+	
 	if (!hlp)
 		return ENOENT;
-	tmpfs_node_t *nodep = hash_table_get_instance(hlp, tmpfs_node_t,
-	    nh_link);
+	
+	tmpfs_node_t *nodep = hash_table_get_inst(hlp, tmpfs_node_t, nh_link);
 
 	/*
@@ -600,12 +597,14 @@
 	 * Lookup the respective TMPFS node.
 	 */
-	unsigned long key[] = {
-		[NODES_KEY_DEV] = service_id,
-		[NODES_KEY_INDEX] = index
+	node_key_t key = {
+		.service_id = service_id,
+		.index = index
 	};
-	link_t *hlp = hash_table_find(&nodes, key);
+	
+	ht_link_t *hlp = hash_table_find(&nodes, &key);
+	
 	if (!hlp)
 		return ENOENT;
-	tmpfs_node_t *nodep = hash_table_get_instance(hlp, tmpfs_node_t, nh_link);
+	tmpfs_node_t *nodep = hash_table_get_inst(hlp, tmpfs_node_t, nh_link);
 	
 	if (size == nodep->size)
@@ -636,13 +635,13 @@
 static int tmpfs_destroy(service_id_t service_id, fs_index_t index)
 {
-	link_t *hlp;
-	unsigned long key[] = {
-		[NODES_KEY_DEV] = service_id,
-		[NODES_KEY_INDEX] = index
+	node_key_t key = {
+		.service_id = service_id,
+		.index = index
 	};
-	hlp = hash_table_find(&nodes, key);
+	
+	ht_link_t *hlp = hash_table_find(&nodes, &key);
 	if (!hlp)
 		return ENOENT;
-	tmpfs_node_t *nodep = hash_table_get_instance(hlp, tmpfs_node_t,
+	tmpfs_node_t *nodep = hash_table_get_inst(hlp, tmpfs_node_t,
 	    nh_link);
 	return tmpfs_destroy_node(FS_NODE(nodep));
Index: uspace/srv/hid/input/gsp.c
===================================================================
--- uspace/srv/hid/input/gsp.c	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/srv/hid/input/gsp.c	(revision 062d9000625057300f609429080872d6492b542e)
@@ -50,24 +50,45 @@
 
 #include <adt/hash_table.h>
+#include <adt/hash.h>
 #include <stdlib.h>
 #include <stdio.h>
 #include "gsp.h"
 
-#define TRANS_TABLE_CHAINS  256
-
 /*
- * Hash table operations for the transition function.
- */
-
-static hash_index_t trans_op_hash(unsigned long key[]);
-static int trans_op_compare(unsigned long key[], hash_count_t keys,
-    link_t *item);
-static void trans_op_remove_callback(link_t *item);
-
-static hash_table_operations_t trans_ops = {
-	.hash = trans_op_hash,
-	.compare = trans_op_compare,
-	.remove_callback = trans_op_remove_callback
+ * Transition function hash table operations.
+ */
+typedef struct {
+	int old_state;
+	int input;
+} trans_key_t;
+
+static size_t trans_key_hash(void *key)
+{
+	trans_key_t *trans_key = (trans_key_t *)key;
+	return hash_combine(trans_key->input, trans_key->old_state);
+}
+
+static size_t trans_hash(const ht_link_t *item)
+{
+	gsp_trans_t *t = hash_table_get_inst(item, gsp_trans_t, link);
+	return hash_combine(t->input, t->old_state);
+}
+
+static bool trans_key_equal(void *key, const ht_link_t *item)
+{
+	trans_key_t *trans_key = (trans_key_t *)key;
+	gsp_trans_t *t = hash_table_get_inst(item, gsp_trans_t, link);
+	
+	return trans_key->input == t->input && trans_key->old_state == t->old_state;
+}
+
+static hash_table_ops_t trans_ops = {
+	.hash = trans_hash,
+	.key_hash = trans_key_hash,
+	.key_equal = trans_key_equal,
+	.equal = 0,
+	.remove_callback = 0
 };
+
 
 static gsp_trans_t *trans_lookup(gsp_t *p, int state, int input);
@@ -75,9 +96,9 @@
 static gsp_trans_t *trans_new(void);
 
-/** Initialise scancode parser. */
+/** Initialize scancode parser. */
 void gsp_init(gsp_t *p)
 {
 	p->states = 1;
-	hash_table_create(&p->trans, TRANS_TABLE_CHAINS, 2, &trans_ops);
+	hash_table_create(&p->trans, 0, 0, &trans_ops);
 }
 
@@ -223,14 +244,15 @@
 static gsp_trans_t *trans_lookup(gsp_t *p, int state, int input)
 {
-	link_t *item;
-	unsigned long key[2];
-
-	key[0] = state;
-	key[1] = input;
-
-	item = hash_table_find(&p->trans, key);
+	ht_link_t *item;
+	
+	trans_key_t key = {
+		.input = input,
+		.old_state = state
+	};
+
+	item = hash_table_find(&p->trans, &key);
 	if (item == NULL) return NULL;
 
-	return hash_table_get_instance(item, gsp_trans_t, link);
+	return hash_table_get_inst(item, gsp_trans_t, link);
 }
 
@@ -242,10 +264,5 @@
 static void trans_insert(gsp_t *p, gsp_trans_t *t)
 {
-	unsigned long key[2];
-
-	key[0] = t->old_state;
-	key[1] = t->input;
-
-	hash_table_insert(&p->trans, key, &t->link);
+	hash_table_insert(&p->trans, &t->link);
 }
 
@@ -264,26 +281,4 @@
 }
 
-/*
- * Transition function hash table operations.
- */
-
-static hash_index_t trans_op_hash(unsigned long key[])
-{
-	return (key[0] * 17 + key[1]) % TRANS_TABLE_CHAINS;
-}
-
-static int trans_op_compare(unsigned long key[], hash_count_t keys,
-    link_t *item)
-{
-	gsp_trans_t *t;
-
-	t = hash_table_get_instance(item, gsp_trans_t, link);
-	return ((key[0] == (unsigned long) t->old_state)
-	    && (key[1] == (unsigned long) t->input));
-}
-
-static void trans_op_remove_callback(link_t *item)
-{
-}
 
 /**
Index: uspace/srv/hid/input/gsp.h
===================================================================
--- uspace/srv/hid/input/gsp.h	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/srv/hid/input/gsp.h	(revision 062d9000625057300f609429080872d6492b542e)
@@ -56,5 +56,5 @@
 /** Scancode parser transition. */
 typedef struct {
-	link_t link;		/**< Link to hash table in @c gsp_t */ 
+	ht_link_t link;		/**< Link to hash table in @c gsp_t */ 
 
 	/* Preconditions */
Index: uspace/srv/ns/service.c
===================================================================
--- uspace/srv/ns/service.c	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/srv/ns/service.c	(revision 062d9000625057300f609429080872d6492b542e)
@@ -40,9 +40,8 @@
 #include "ns.h"
 
-#define SERVICE_HASH_TABLE_CHAINS  20
 
 /** Service hash table item. */
 typedef struct {
-	link_t link;
+	ht_link_t link;
 	sysarg_t service;        /**< Service ID. */
 	sysarg_t phone;          /**< Phone registered with the service. */
@@ -50,63 +49,29 @@
 } hashed_service_t;
 
-/** Compute hash index into service hash table.
- *
- * @param key Pointer keys. However, only the first key (i.e. service number)
- *            is used to compute the hash index.
- *
- * @return Hash index corresponding to key[0].
- *
- */
-static hash_index_t service_hash(unsigned long key[])
+
+static size_t service_key_hash(void *key)
 {
-	assert(key);
-	return (key[0] % SERVICE_HASH_TABLE_CHAINS);
+	return *(sysarg_t*)key;
 }
 
-/** Compare a key with hashed item.
- *
- * This compare function always ignores the third key.
- * It exists only to make it possible to remove records
- * originating from connection with key[1] in_phone_hash
- * value. Note that this is close to being classified
- * as a nasty hack.
- *
- * @param key  Array of keys.
- * @param keys Must be lesser or equal to 3.
- * @param item Pointer to a hash table item.
- *
- * @return Non-zero if the key matches the item, zero otherwise.
- *
- */
-static int service_compare(unsigned long key[], hash_count_t keys, link_t *item)
+static size_t service_hash(const ht_link_t *item)
 {
-	assert(key);
-	assert(keys <= 3);
-	assert(item);
-	
-	hashed_service_t *hs = hash_table_get_instance(item, hashed_service_t, link);
-	
-	if (keys == 2)
-		return ((key[0] == hs->service) && (key[1] == hs->in_phone_hash));
-	else
-		return (key[0] == hs->service);
+	hashed_service_t *hs = hash_table_get_inst(item, hashed_service_t, link);
+	return hs->service;
 }
 
-/** Perform actions after removal of item from the hash table.
- *
- * @param item Item that was removed from the hash table.
- *
- */
-static void service_remove(link_t *item)
+static bool service_key_equal(void *key, const ht_link_t *item)
 {
-	assert(item);
-	free(hash_table_get_instance(item, hashed_service_t, link));
+	hashed_service_t *hs = hash_table_get_inst(item, hashed_service_t, link);
+	return hs->service == *(sysarg_t*)key;
 }
 
 /** Operations for service hash table. */
-static hash_table_operations_t service_hash_table_ops = {
+static hash_table_ops_t service_hash_table_ops = {
 	.hash = service_hash,
-	.compare = service_compare,
-	.remove_callback = service_remove
+	.key_hash = service_key_hash,
+	.key_equal = service_key_equal,
+	.equal = 0,
+	.remove_callback = 0
 };
 
@@ -127,6 +92,5 @@
 int service_init(void)
 {
-	if (!hash_table_create(&service_hash_table, SERVICE_HASH_TABLE_CHAINS,
-	    3, &service_hash_table_ops)) {
+	if (!hash_table_create(&service_hash_table, 0, 0, &service_hash_table_ops)) {
 		printf(NAME ": No memory available for services\n");
 		return ENOMEM;
@@ -145,15 +109,9 @@
 		pending_conn_t *pr = list_get_instance(cur, pending_conn_t, link);
 		
-		unsigned long keys[3] = {
-			pr->service,
-			0,
-			0
-		};
-		
-		link_t *link = hash_table_find(&service_hash_table, keys);
+		ht_link_t *link = hash_table_find(&service_hash_table, &pr->service);
 		if (!link)
 			continue;
 		
-		hashed_service_t *hs = hash_table_get_instance(link, hashed_service_t, link);
+		hashed_service_t *hs = hash_table_get_inst(link, hashed_service_t, link);
 		(void) ipc_forward_fast(pr->callid, hs->phone, pr->arg2,
 		    pr->arg3, 0, IPC_FF_NONE);
@@ -176,11 +134,5 @@
 int register_service(sysarg_t service, sysarg_t phone, ipc_call_t *call)
 {
-	unsigned long keys[3] = {
-		service,
-		call->in_phone_hash,
-		0
-	};
-	
-	if (hash_table_find(&service_hash_table, keys))
+	if (hash_table_find(&service_hash_table, &service))
 		return EEXISTS;
 	
@@ -189,9 +141,8 @@
 		return ENOMEM;
 	
-	link_initialize(&hs->link);
 	hs->service = service;
 	hs->phone = phone;
 	hs->in_phone_hash = call->in_phone_hash;
-	hash_table_insert(&service_hash_table, keys, &hs->link);
+	hash_table_insert(&service_hash_table, &hs->link);
 	
 	return EOK;
@@ -210,11 +161,6 @@
 {
 	sysarg_t retval;
-	unsigned long keys[3] = {
-		service,
-		0,
-		0
-	};
 	
-	link_t *link = hash_table_find(&service_hash_table, keys);
+	ht_link_t *link = hash_table_find(&service_hash_table, &service);
 	if (!link) {
 		if (IPC_GET_ARG4(*call) & IPC_FLAG_BLOCKING) {
@@ -239,5 +185,5 @@
 	}
 	
-	hashed_service_t *hs = hash_table_get_instance(link, hashed_service_t, link);
+	hashed_service_t *hs = hash_table_get_inst(link, hashed_service_t, link);
 	(void) ipc_forward_fast(callid, hs->phone, IPC_GET_ARG2(*call),
 	    IPC_GET_ARG3(*call), 0, IPC_FF_NONE);
Index: uspace/srv/ns/task.c
===================================================================
--- uspace/srv/ns/task.c	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/srv/ns/task.c	(revision 062d9000625057300f609429080872d6492b542e)
@@ -43,6 +43,4 @@
 #include "ns.h"
 
-#define TASK_HASH_TABLE_CHAINS  256
-#define P2I_HASH_TABLE_CHAINS   256
 
 /* TODO:
@@ -55,5 +53,5 @@
 /** Task hash table item. */
 typedef struct {
-	link_t link;
+	ht_link_t link;
 	
 	task_id_t id;    /**< Task ID. */
@@ -63,57 +61,34 @@
 } hashed_task_t;
 
-/** Compute hash index into task hash table.
- *
- * @param key Pointer keys. However, only the first key (i.e. truncated task
- *            number) is used to compute the hash index.
- *
- * @return Hash index corresponding to key[0].
- *
- */
-static hash_index_t task_hash(unsigned long key[])
-{
-	assert(key);
-	return (LOWER32(key[0]) % TASK_HASH_TABLE_CHAINS);
-}
-
-/** Compare a key with hashed item.
- *
- * @param key  Array of keys.
- * @param keys Must be less than or equal to 2.
- * @param item Pointer to a hash table item.
- *
- * @return Non-zero if the key matches the item, zero otherwise.
- *
- */
-static int task_compare(unsigned long key[], hash_count_t keys, link_t *item)
-{
-	assert(key);
-	assert(keys <= 2);
-	assert(item);
-	
-	hashed_task_t *ht = hash_table_get_instance(item, hashed_task_t, link);
-	
-	if (keys == 2)
-		return ((LOWER32(key[1]) == UPPER32(ht->id))
-		    && (LOWER32(key[0]) == LOWER32(ht->id)));
-	else
-		return (LOWER32(key[0]) == LOWER32(ht->id));
-}
-
-/** Perform actions after removal of item from the hash table.
- *
- * @param item Item that was removed from the hash table.
- *
- */
-static void task_remove(link_t *item)
-{
-	assert(item);
-	free(hash_table_get_instance(item, hashed_task_t, link));
+
+static size_t task_key_hash(void *key)
+{
+	return *(task_id_t*)key;
+}
+
+static size_t task_hash(const ht_link_t  *item)
+{
+	hashed_task_t *ht = hash_table_get_inst(item, hashed_task_t, link);
+	return ht->id;
+}
+
+static bool task_key_equal(void *key, const ht_link_t *item)
+{
+	hashed_task_t *ht = hash_table_get_inst(item, hashed_task_t, link);
+	return ht->id == *(task_id_t*)key;
+}
+
+/** Perform actions after removal of item from the hash table. */
+static void task_remove(ht_link_t *item)
+{
+	free(hash_table_get_inst(item, hashed_task_t, link));
 }
 
 /** Operations for task hash table. */
-static hash_table_operations_t task_hash_table_ops = {
+static hash_table_ops_t task_hash_table_ops = {
 	.hash = task_hash,
-	.compare = task_compare,
+	.key_hash = task_key_hash,
+	.key_equal = task_key_equal,
+	.equal = 0,
 	.remove_callback = task_remove
 };
@@ -123,57 +98,48 @@
 
 typedef struct {
-	link_t link;
+	ht_link_t link;
 	sysarg_t in_phone_hash;  /**< Incoming phone hash. */
 	task_id_t id;            /**< Task ID. */
 } p2i_entry_t;
 
-/** Compute hash index into task hash table.
- *
- * @param key Array of keys.
- *
- * @return Hash index corresponding to key[0].
- *
- */
-static hash_index_t p2i_hash(unsigned long key[])
-{
-	assert(key);
-	return (key[0] % TASK_HASH_TABLE_CHAINS);
-}
-
-/** Compare a key with hashed item.
- *
- * @param key  Array of keys.
- * @param keys Must be less than or equal to 1.
- * @param item Pointer to a hash table item.
- *
- * @return Non-zero if the key matches the item, zero otherwise.
- *
- */
-static int p2i_compare(unsigned long key[], hash_count_t keys, link_t *item)
-{
-	assert(key);
-	assert(keys == 1);
+/* phone-to-id hash table operations */
+
+static size_t p2i_key_hash(void *key)
+{
+	sysarg_t in_phone_hash = *(sysarg_t*)key;
+	return in_phone_hash;
+}
+
+static size_t p2i_hash(const ht_link_t *item)
+{
+	p2i_entry_t *entry = hash_table_get_inst(item, p2i_entry_t, link);
+	return entry->in_phone_hash;
+}
+
+static bool p2i_key_equal(void *key, const ht_link_t *item)
+{
+	sysarg_t in_phone_hash = *(sysarg_t*)key;
+	p2i_entry_t *entry = hash_table_get_inst(item, p2i_entry_t, link);
+	
+	return (in_phone_hash == entry->in_phone_hash);
+}
+
+/** Perform actions after removal of item from the hash table.
+ *
+ * @param item Item that was removed from the hash table.
+ *
+ */
+static void p2i_remove(ht_link_t *item)
+{
 	assert(item);
-	
-	p2i_entry_t *entry = hash_table_get_instance(item, p2i_entry_t, link);
-	
-	return (key[0] == entry->in_phone_hash);
-}
-
-/** Perform actions after removal of item from the hash table.
- *
- * @param item Item that was removed from the hash table.
- *
- */
-static void p2i_remove(link_t *item)
-{
-	assert(item);
-	free(hash_table_get_instance(item, p2i_entry_t, link));
+	free(hash_table_get_inst(item, p2i_entry_t, link));
 }
 
 /** Operations for task hash table. */
-static hash_table_operations_t p2i_ops = {
+static hash_table_ops_t p2i_ops = {
 	.hash = p2i_hash,
-	.compare = p2i_compare,
+	.key_hash = p2i_key_hash,
+	.key_equal = p2i_key_equal,
+	.equal = 0,
 	.remove_callback = p2i_remove
 };
@@ -193,12 +159,10 @@
 int task_init(void)
 {
-	if (!hash_table_create(&task_hash_table, TASK_HASH_TABLE_CHAINS,
-	    2, &task_hash_table_ops)) {
+	if (!hash_table_create(&task_hash_table, 0, 0, &task_hash_table_ops)) {
 		printf(NAME ": No memory available for tasks\n");
 		return ENOMEM;
 	}
 	
-	if (!hash_table_create(&phone_to_id, P2I_HASH_TABLE_CHAINS,
-	    1, &p2i_ops)) {
+	if (!hash_table_create(&phone_to_id, 0, 0, &p2i_ops)) {
 		printf(NAME ": No memory available for tasks\n");
 		return ENOMEM;
@@ -218,14 +182,9 @@
 		pending_wait_t *pr = list_get_instance(cur, pending_wait_t, link);
 		
-		unsigned long keys[2] = {
-			LOWER32(pr->id),
-			UPPER32(pr->id)
-		};
-		
-		link_t *link = hash_table_find(&task_hash_table, keys);
+		ht_link_t *link = hash_table_find(&task_hash_table, &pr->id);
 		if (!link)
 			continue;
 		
-		hashed_task_t *ht = hash_table_get_instance(link, hashed_task_t, link);
+		hashed_task_t *ht = hash_table_get_inst(link, hashed_task_t, link);
 		if (!ht->finished)
 			continue;
@@ -238,5 +197,5 @@
 		}
 		
-		hash_table_remove(&task_hash_table, keys, 2);
+		hash_table_remove(&task_hash_table, &pr->id);
 		list_remove(cur);
 		free(pr);
@@ -250,12 +209,7 @@
 	task_exit_t texit;
 	
-	unsigned long keys[2] = {
-		LOWER32(id),
-		UPPER32(id)
-	};
-	
-	link_t *link = hash_table_find(&task_hash_table, keys);
+	ht_link_t *link = hash_table_find(&task_hash_table, &id);
 	hashed_task_t *ht = (link != NULL) ?
-	    hash_table_get_instance(link, hashed_task_t, link) : NULL;
+	    hash_table_get_inst(link, hashed_task_t, link) : NULL;
 	
 	if (ht == NULL) {
@@ -281,5 +235,5 @@
 	}
 	
-	hash_table_remove(&task_hash_table, keys, 2);
+	hash_table_remove_item(&task_hash_table, link);
 	retval = EOK;
 	
@@ -293,10 +247,8 @@
 int ns_task_id_intro(ipc_call_t *call)
 {
-	unsigned long keys[2];
 	
 	task_id_t id = MERGE_LOUP32(IPC_GET_ARG1(*call), IPC_GET_ARG2(*call));
-	keys[0] = call->in_phone_hash;
-	
-	link_t *link = hash_table_find(&phone_to_id, keys);
+
+	ht_link_t *link = hash_table_find(&phone_to_id, &call->in_phone_hash);
 	if (link != NULL)
 		return EEXISTS;
@@ -314,8 +266,7 @@
 	 */
 	
-	link_initialize(&entry->link);
 	entry->in_phone_hash = call->in_phone_hash;
 	entry->id = id;
-	hash_table_insert(&phone_to_id, keys, &entry->link);
+	hash_table_insert(&phone_to_id, &entry->link);
 	
 	/*
@@ -323,13 +274,9 @@
 	 */
 	
-	keys[0] = LOWER32(id);
-	keys[1] = UPPER32(id);
-	
-	link_initialize(&ht->link);
 	ht->id = id;
 	ht->finished = false;
 	ht->have_rval = false;
 	ht->retval = -1;
-	hash_table_insert(&task_hash_table, keys, &ht->link);
+	hash_table_insert(&task_hash_table, &ht->link);
 	
 	return EOK;
@@ -338,11 +285,9 @@
 static int get_id_by_phone(sysarg_t phone_hash, task_id_t *id)
 {
-	unsigned long keys[1] = {phone_hash};
-	
-	link_t *link = hash_table_find(&phone_to_id, keys);
+	ht_link_t *link = hash_table_find(&phone_to_id, &phone_hash);
 	if (link == NULL)
 		return ENOENT;
 	
-	p2i_entry_t *entry = hash_table_get_instance(link, p2i_entry_t, link);
+	p2i_entry_t *entry = hash_table_get_inst(link, p2i_entry_t, link);
 	*id = entry->id;
 	
@@ -357,12 +302,7 @@
 		return rc;
 	
-	unsigned long keys[2] = {
-		LOWER32(id),
-		UPPER32(id)
-	};
-	
-	link_t *link = hash_table_find(&task_hash_table, keys);
+	ht_link_t *link = hash_table_find(&task_hash_table, &id);
 	hashed_task_t *ht = (link != NULL) ?
-	    hash_table_get_instance(link, hashed_task_t, link) : NULL;
+	    hash_table_get_inst(link, hashed_task_t, link) : NULL;
 	
 	if ((ht == NULL) || (ht->finished))
@@ -378,6 +318,4 @@
 int ns_task_disconnect(ipc_call_t *call)
 {
-	unsigned long keys[2];
-	
 	task_id_t id;
 	int rc = get_id_by_phone(call->in_phone_hash, &id);
@@ -386,16 +324,12 @@
 	
 	/* Delete from phone-to-id map. */
-	keys[0] = call->in_phone_hash;
-	hash_table_remove(&phone_to_id, keys, 1);
+	hash_table_remove(&phone_to_id, &call->in_phone_hash);
 	
 	/* Mark task as finished. */
-	keys[0] = LOWER32(id);
-	keys[1] = UPPER32(id);
-	
-	link_t *link = hash_table_find(&task_hash_table, keys);
-	hashed_task_t *ht =
-	    hash_table_get_instance(link, hashed_task_t, link);
-	if (ht == NULL)
+	ht_link_t *link = hash_table_find(&task_hash_table, &id);
+	if (link == NULL)
 		return EOK;
+
+	hashed_task_t *ht = hash_table_get_inst(link, hashed_task_t, link);
 	
 	ht->finished = true;
Index: uspace/srv/vfs/vfs.h
===================================================================
--- uspace/srv/vfs/vfs.h	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/srv/vfs/vfs.h	(revision 062d9000625057300f609429080872d6492b542e)
@@ -36,4 +36,5 @@
 #include <async.h>
 #include <adt/list.h>
+#include <adt/hash_table.h>
 #include <fibril_synch.h>
 #include <sys/types.h>
@@ -112,5 +113,5 @@
 	unsigned lnkcnt;
 
-	link_t nh_link;		/**< Node hash-table link. */
+	ht_link_t nh_link;		/**< Node hash-table link. */
 
 	vfs_node_type_t type;	/**< Partial info about the node type. */
Index: uspace/srv/vfs/vfs_node.c
===================================================================
--- uspace/srv/vfs/vfs_node.c	(revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13)
+++ uspace/srv/vfs/vfs_node.c	(revision 062d9000625057300f609429080872d6492b542e)
@@ -41,4 +41,5 @@
 #include <fibril_synch.h>
 #include <adt/hash_table.h>
+#include <adt/hash.h>
 #include <assert.h>
 #include <async.h>
@@ -58,13 +59,16 @@
 #define KEY_INDEX	2
 
-static hash_index_t nodes_hash(unsigned long []);
-static int nodes_compare(unsigned long [], hash_count_t, link_t *);
-static void nodes_remove_callback(link_t *);
+static size_t nodes_key_hash(void *);
+static size_t nodes_hash(const ht_link_t *);
+static bool nodes_key_equal(void *, const ht_link_t *);
+static vfs_triplet_t node_triplet(vfs_node_t *node);
 
 /** VFS node hash table operations. */
-hash_table_operations_t nodes_ops = {
+hash_table_ops_t nodes_ops = {
 	.hash = nodes_hash,
-	.compare = nodes_compare,
-	.remove_callback = nodes_remove_callback
+	.key_hash = nodes_key_hash,
+	.key_equal = nodes_key_equal,
+	.equal = 0,
+	.remove_callback = 0,
 };
 
@@ -75,5 +79,5 @@
 bool vfs_nodes_init(void)
 {
-	return hash_table_create(&nodes, NODES_BUCKETS, 3, &nodes_ops);
+	return hash_table_create(&nodes, 0, 0, &nodes_ops);
 }
 
@@ -114,11 +118,5 @@
 		 */
 		
-		unsigned long key[] = {
-			[KEY_FS_HANDLE] = node->fs_handle,
-			[KEY_DEV_HANDLE] = node->service_id,
-			[KEY_INDEX] = node->index
-		};
-		
-		hash_table_remove(&nodes, key, 3);
+		hash_table_remove_item(&nodes, &node->nh_link);
 		free_vfs_node = true;
 		
@@ -158,10 +156,5 @@
 {
 	fibril_mutex_lock(&nodes_mutex);
-	unsigned long key[] = {
-		[KEY_FS_HANDLE] = node->fs_handle,
-		[KEY_DEV_HANDLE] = node->service_id,
-		[KEY_INDEX] = node->index
-	};
-	hash_table_remove(&nodes, key, 3);
+	hash_table_remove_item(&nodes, &node->nh_link);
 	fibril_mutex_unlock(&nodes_mutex);
 	free(node);
@@ -182,14 +175,8 @@
 vfs_node_t *vfs_node_get(vfs_lookup_res_t *result)
 {
-	unsigned long key[] = {
-		[KEY_FS_HANDLE] = result->triplet.fs_handle,
-		[KEY_DEV_HANDLE] = result->triplet.service_id,
-		[KEY_INDEX] = result->triplet.index
-	};
-	link_t *tmp;
 	vfs_node_t *node;
 
 	fibril_mutex_lock(&nodes_mutex);
-	tmp = hash_table_find(&nodes, key);
+	ht_link_t *tmp = hash_table_find(&nodes, &result->triplet);
 	if (!tmp) {
 		node = (vfs_node_t *) malloc(sizeof(vfs_node_t));
@@ -205,9 +192,8 @@
 		node->lnkcnt = result->lnkcnt;
 		node->type = result->type;
-		link_initialize(&node->nh_link);
 		fibril_rwlock_initialize(&node->contents_rwlock);
-		hash_table_insert(&nodes, key, &node->nh_link);
+		hash_table_insert(&nodes, &node->nh_link);
 	} else {
-		node = hash_table_get_instance(tmp, vfs_node_t, nh_link);
+		node = hash_table_get_inst(tmp, vfs_node_t, nh_link);
 		if (node->type == VFS_NODE_UNKNOWN &&
 		    result->type != VFS_NODE_UNKNOWN) {
@@ -240,24 +226,4 @@
 }
 
-hash_index_t nodes_hash(unsigned long key[])
-{
-	hash_index_t a = key[KEY_FS_HANDLE] << (NODES_BUCKETS_LOG / 4);
-	hash_index_t b = (a | key[KEY_DEV_HANDLE]) << (NODES_BUCKETS_LOG / 2);
-	
-	return (b | key[KEY_INDEX]) & (NODES_BUCKETS - 1);
-}
-
-int nodes_compare(unsigned long key[], hash_count_t keys, link_t *item)
-{
-	vfs_node_t *node = hash_table_get_instance(item, vfs_node_t, nh_link);
-	return (node->fs_handle == (fs_handle_t) key[KEY_FS_HANDLE]) &&
-	    (node->service_id == key[KEY_DEV_HANDLE]) &&
-	    (node->index == key[KEY_INDEX]);
-}
-
-void nodes_remove_callback(link_t *item)
-{
-}
-
 struct refcnt_data {
 	/** Sum of all reference counts for this file system instance. */
@@ -267,7 +233,7 @@
 };
 
-static void refcnt_visitor(link_t *item, void *arg)
-{
-	vfs_node_t *node = hash_table_get_instance(item, vfs_node_t, nh_link);
+static bool refcnt_visitor(ht_link_t *item, void *arg)
+{
+	vfs_node_t *node = hash_table_get_inst(item, vfs_node_t, nh_link);
 	struct refcnt_data *rd = (void *) arg;
 
@@ -275,4 +241,6 @@
 	    (node->service_id == rd->service_id))
 		rd->refcnt += node->refcnt;
+	
+	return true;
 }
 
@@ -315,4 +283,39 @@
 }
 
+
+static size_t nodes_key_hash(void *key)
+{
+	vfs_triplet_t *tri = key;
+	size_t hash = hash_combine(tri->fs_handle, tri->index);
+	return hash_combine(hash, tri->service_id);
+}
+
+static size_t nodes_hash(const ht_link_t *item)
+{
+	vfs_node_t *node = hash_table_get_inst(item, vfs_node_t, nh_link);
+	vfs_triplet_t tri = node_triplet(node);
+	return nodes_key_hash(&tri);
+}
+
+static bool nodes_key_equal(void *key, const ht_link_t *item)
+{
+	vfs_triplet_t *tri = key;
+	vfs_node_t *node = hash_table_get_inst(item, vfs_node_t, nh_link);
+	return node->fs_handle == tri->fs_handle 
+		&& node->service_id == tri->service_id
+		&& node->index == tri->index;
+}
+
+static inline vfs_triplet_t node_triplet(vfs_node_t *node)
+{
+	vfs_triplet_t tri = {
+		.fs_handle = node->fs_handle,
+		.service_id = node->service_id,
+		.index = node->index
+	};
+	
+	return tri;
+}
+
 /**
  * @}
