Index: kernel/generic/src/proc/thread.c
===================================================================
--- kernel/generic/src/proc/thread.c	(revision 7b63b6b0ed5eb2c8d7afc8e459b93343244389d7)
+++ kernel/generic/src/proc/thread.c	(revision 83a5cba0066dd013f87382960bf1e6ac17b2ea89)
@@ -52,5 +52,5 @@
 #include <func.h>
 #include <context.h>
-#include <adt/btree.h>
+#include <adt/avl.h>
 #include <adt/list.h>
 #include <time/clock.h>
@@ -82,5 +82,5 @@
 }; 
 
-/** Lock protecting the threads_btree B+tree.
+/** Lock protecting the threads_tree AVL tree.
  *
  * For locking rules, see declaration thereof.
@@ -88,10 +88,10 @@
 SPINLOCK_INITIALIZE(threads_lock);
 
-/** B+tree of all threads.
- *
- * When a thread is found in the threads_btree B+tree, it is guaranteed to
+/** ALV tree of all threads.
+ *
+ * When a thread is found in the threads_tree AVL tree, it is guaranteed to
  * exist as long as the threads_lock is held.
  */
-btree_t threads_btree;		
+avltree_t threads_tree;		
 
 SPINLOCK_INITIALIZE(tidlock);
@@ -213,5 +213,5 @@
 #endif
 
-	btree_create(&threads_btree);
+	avltree_create(&threads_tree);
 }
 
@@ -340,4 +340,7 @@
 	t->fpu_context_engaged = 0;
 
+	avltree_node_initialize(&t->threads_tree_node);
+	t->threads_tree_node.key = (uintptr_t) t;
+
 	/* might depend on previous initialization */
 	thread_create_arch(t);	
@@ -369,5 +372,5 @@
 
 	spinlock_lock(&threads_lock);
-	btree_remove(&threads_btree, (btree_key_t) ((uintptr_t ) t), NULL);
+	avltree_delete(&threads_tree, &t->threads_tree_node);
 	spinlock_unlock(&threads_lock);
 
@@ -392,5 +395,5 @@
  *
  * Attach the thread structure to the current task and make it visible in the
- * threads_btree.
+ * threads_tree.
  *
  * @param t	Thread to be attached to the task.
@@ -415,6 +418,5 @@
 	 */
 	spinlock_lock(&threads_lock);
-	btree_insert(&threads_btree, (btree_key_t) ((uintptr_t) t), (void *) t,
-	    NULL);
+	avltree_insert(&threads_tree, &t->threads_tree_node);
 	spinlock_unlock(&threads_lock);
 	
@@ -576,8 +578,32 @@
 }
 
+static void thread_walker(avltree_node_t *node)
+{
+	thread_t *t;
+		
+	t = avltree_get_instance(node, thread_t, threads_tree_node);
+
+	uint64_t cycles;
+	char suffix;
+	order(t->cycles, &cycles, &suffix);
+			
+	printf("%-6llu %-10s %#10zx %-8s %#10zx %-3ld %#10zx %#10zx %9llu%c ",
+	    t->tid, t->name, t, thread_states[t->state], t->task,
+	    t->task->context, t->thread_code, t->kstack, cycles, suffix);
+			
+	if (t->cpu)
+		printf("%-4zd", t->cpu->id);
+	else
+		printf("none");
+			
+	if (t->state == Sleeping)
+		printf(" %#10zx", t->sleep_queue);
+			
+	printf("\n");
+}
+
 /** Print list of threads debug info */
 void thread_print_list(void)
 {
-	link_t *cur;
 	ipl_t ipl;
 	
@@ -591,35 +617,5 @@
 	    "-- ---------- ---------- ---- ---------\n");
 
-	for (cur = threads_btree.leaf_head.next;
-	    cur != &threads_btree.leaf_head; cur = cur->next) {
-		btree_node_t *node;
-		unsigned int i;
-
-		node = list_get_instance(cur, btree_node_t, leaf_link);
-		for (i = 0; i < node->keys; i++) {
-			thread_t *t;
-		
-			t = (thread_t *) node->value[i];
-			
-			uint64_t cycles;
-			char suffix;
-			order(t->cycles, &cycles, &suffix);
-			
-			printf("%-6llu %-10s %#10zx %-8s %#10zx %-3ld %#10zx "
-			    "%#10zx %9llu%c ", t->tid, t->name, t,
-			    thread_states[t->state], t->task, t->task->context,
-			    t->thread_code, t->kstack, cycles, suffix);
-			
-			if (t->cpu)
-				printf("%-4zd", t->cpu->id);
-			else
-				printf("none");
-			
-			if (t->state == Sleeping)
-				printf(" %#10zx", t->sleep_queue);
-			
-			printf("\n");
-		}
-	}
+	avltree_walk(&threads_tree, thread_walker);
 
 	spinlock_unlock(&threads_lock);
@@ -638,8 +634,9 @@
 bool thread_exists(thread_t *t)
 {
-	btree_node_t *leaf;
-	
-	return btree_search(&threads_btree, (btree_key_t) ((uintptr_t) t),
-	    &leaf) != NULL;
+	avltree_node_t *node;
+
+	node = avltree_search(&threads_tree, (avltree_key_t) ((uintptr_t) t));
+	
+	return node != NULL;
 }