Changeset ef1eab7 in mainline for kernel/generic/include

Timestamp:

2018-11-03T21:36:39Z (7 years ago)

Author:

Jiri Svoboda <jiri@…>

Branches:

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

Children:

aab5e46

Parents:

ad2cf04

Message:

Replace AVL trees in kernel with ordered dictionary.

Location:

kernel/generic/include

Files:

• adt/avl.h (deleted)
• proc/task.h (modified) (3 diffs)
• proc/thread.h (modified) (3 diffs)

kernel/generic/include/proc/task.h

@@ -44 +44 @@
 #include <synch/futex.h>
 #include <synch/workqueue.h>
-#include <adt/avl.h>
 #include <adt/btree.h>
 #include <adt/cht.h>
 #include <adt/list.h>
+#include <adt/odict.h>
 #include <security/perm.h>
 #include <arch/proc/task.h>
@@ -70 +70 @@
 /** Task structure. */
 typedef struct task {
-        /** Task's linkage for the tasks_tree AVL tree. */
-        avltree_node_t tasks_tree_node;
+        /** Link to @c tasks ordered dictionary */
+        odlink_t ltasks;
 
         /** Task lock.
@@ -146 +146 @@
 } task_t;
 
+/** Synchronize access to @c tasks */
 IRQ_SPINLOCK_EXTERN(tasks_lock);
-extern avltree_t tasks_tree;
+/** Ordered dictionary of all tasks by ID (of task_t structures) */
+extern odict_t tasks;
 
 extern void task_init(void);

kernel/generic/include/proc/thread.h

@@ -42 +42 @@
 #include <synch/spinlock.h>
 #include <synch/rcu_types.h>
-#include <adt/avl.h>
+#include <adt/odict.h>
 #include <mm/slab.h>
 #include <arch/cpu.h>
@@ -75 +75 @@
         link_t th_link;  /**< Links to threads within containing task. */
 
-        /** Threads linkage to the threads_tree. */
-        avltree_node_t threads_tree_node;
+        /** Link to @c threads ordered dictionary. */
+        odlink_t lthreads;
 
         /** Lock protecting thread structure.
@@ -224 +224 @@
 } thread_t;
 
-/** Thread list lock.
- *
- * This lock protects the threads_tree.
- * Must be acquired before T.lock for each T of type thread_t.
- *
- */
 IRQ_SPINLOCK_EXTERN(threads_lock);
-
-/** AVL tree containing all threads. */
-extern avltree_t threads_tree;
+extern odict_t threads;
 
 extern void thread_init(void);