Changeset 5dcee525 in mainline for kernel/generic/src/proc/thread.c

Timestamp:

2007-07-29T13:50:20Z (17 years ago)

Author:

Jakub Jermar <jakub@…>

Branches:

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

Children:

83a5cba

Parents:

d1e9321

Message:

Replace the threads_btree B+tree with an AVL tree. The new variable is called
threads_tree. For printing list of threads, use the new AVL tree walker
mechanism.

This solves half of ticket #48.

File:

• kernel/generic/src/proc/thread.c (modified) (11 diffs)

kernel/generic/src/proc/thread.c

@@ -52 +52 @@
 #include <func.h>
 #include <context.h>
-#include <adt/btree.h>
+#include <adt/avl.h>
 #include <adt/list.h>
 #include <time/clock.h>
@@ -82 +82 @@
 }; 
 
-/** Lock protecting the threads_btree B+tree.
+/** Lock protecting the threads_tree AVL tree.
  *
  * For locking rules, see declaration thereof.
@@ -88 +88 @@
 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 +213 @@
 #endif
 
-        btree_create(&threads_btree);
+        avltree_create(&threads_tree);
 }
 
@@ -340 +340 @@
         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 +372 @@
 
         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 +395 @@
  *
  * 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 +418 @@
          */
         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 +578 @@
 }
 
+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 +617 @@
             "-- ---------- ---------- ---- ---------\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 +634 @@
 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;
 }