WebSVN – HelenOS – Diff – /trunk/kernel/generic/src/proc/thread.c/

 #include <synch/waitq.h>
 #include <synch/rwlock.h>
 #include <cpu.h>
 #include <func.h>
 #include <context.h>
-#include <adt/btree.h>
+#include <adt/avl.h>
 #include <adt/list.h>
 #include <time/clock.h>
 #include <time/timeout.h>
 #include <config.h>
 #include <arch/interrupt.h>
     "Entering",
     "Exiting",
     "Lingering"
 };
-/** Lock protecting the threads_btree B+tree.
+/** Lock protecting the threads_tree AVL tree.
+ *
  * For locking rules, see declaration thereof.
  */
 SPINLOCK_INITIALIZE(threads_lock);
-/** B+tree of all threads.
+/** ALV tree of all threads.
+ *
- * When a thread is found in the threads_btree B+tree, it is guaranteed to
+ * 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);
 thread_id_t last_tid = 0;
 static slab_cache_t *thread_slab;
 #ifdef ARCH_HAS_FPU
     fpu_context_slab = slab_cache_create("fpu_slab", sizeof(fpu_context_t),
         FPU_CONTEXT_ALIGN, NULL, NULL, 0);
 #endif
-    btree_create(&threads_btree);
+    avltree_create(&threads_tree);
+}
 /** Make thread ready
+ *
  * Switch thread t to the ready state.
     t->task = task;
     t->fpu_context_exists = 0;
     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);
     if (!(flags & THREAD_FLAG_NOATTACH))
         thread_attach(t, task);
     spinlock_unlock(&t->cpu->lock);
     spinlock_unlock(&t->lock);
     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);
     /*
      * Detach from the containing task.
      */
+}
 /** Make the thread visible to the system.
+ *
  * 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.
  * @param task  Task to which the thread is to be attached.
  */
 void thread_attach(thread_t *t, task_t *task)
     /*
      * Register this thread in the system-wide list.
      */
     spinlock_lock(&threads_lock);
-    btree_insert(&threads_btree, (btree_key_t) ((uintptr_t) t), (void *) t,
+    avltree_insert(&threads_tree, &t->threads_tree_node);
-        NULL);
     spinlock_unlock(&threads_lock);
     interrupts_restore(ipl);
+}
     THREAD->call_me_with = call_me_with;
     spinlock_unlock(&THREAD->lock);
     interrupts_restore(ipl);
+}
+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;
     /* Messing with thread structures, avoid deadlock */
     ipl = interrupts_disable();
     spinlock_lock(&threads_lock);
     printf("tid    name       address    state    task       ctx code    "
         "   stack      cycles     cpu  waitqueue\n");
     printf("------ ---------- ---------- -------- ---------- --- --------"
         "-- ---------- ---------- ---- ---------\n");
-    for (cur = threads_btree.leaf_head.next;
+    avltree_walk(&threads_tree, thread_walker);
-        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");
-        }
-    }
     spinlock_unlock(&threads_lock);
     interrupts_restore(ipl);
+}
+ *
  * @return True if thread t is known to the system, false otherwise.
  */
 bool thread_exists(thread_t *t)
+{
-    btree_node_t *leaf;
+    avltree_node_t *node;
+    node = avltree_search(&threads_tree, (avltree_key_t) ((uintptr_t) t));
-    return btree_search(&threads_btree, (btree_key_t) ((uintptr_t) t),
-        &leaf) != NULL;
+    return node != NULL;
+}
 /** Update accounting of current thread.
+ *

Subversion Repositories HelenOS

(root)/trunk/kernel/generic/src/proc/thread.c/ – Rev 2487 → 2502