litmus: add qsort list manipulation function

The adaptive optimizer needs to sort lists.

1 files changed, 40 insertions, 0 deletions

diff --git a/kernel/litmus.c b/kernel/litmus.c
index c05a20bde7..131fc5039e 100644
--- a/kernel/litmus.c
+++ b/kernel/litmus.c
@@ -679,6 +679,46 @@ void exit_litmus(struct task_struct *dead_tsk)
         curr_sched_plugin->tear_down(dead_tsk);
 }
 
+void list_qsort(struct list_head* list, list_cmp_t less_than)
+{
+        struct list_head lt;
+        struct list_head geq;
+        struct list_head *pos, *extra, *pivot;
+        int n_lt = 0, n_geq = 0;
+        BUG_ON(!list);
+
+        if (list->next == list)
+                return;
+
+        INIT_LIST_HEAD(&lt);
+        INIT_LIST_HEAD(&geq);
+
+        pivot = list->next;
+        list_for_each_safe(pos, extra, list) {
+                list_del(pos);
+                if (less_than(pos, pivot)) {
+                        list_add(pos, &lt);
+                        n_lt++;
+                } else {
+                        list_add(pos, &geq);
+                        n_geq++;
+                }
+        }
+        if (n_lt < n_geq) {
+                if (n_lt > 1)
+                        list_qsort(&lt, less_than);
+                if (n_geq > 1)
+                        list_qsort(&geq, less_than);
+        } else {
+                if (n_geq > 1)
+                        list_qsort(&geq, less_than);
+                if (n_lt > 1)
+                        list_qsort(&lt, less_than);
+        }
+        list_splice(&geq, list);
+        list_splice(&lt, list);
+}
+
 #ifdef CONFIG_MAGIC_SYSRQ
 /* We offer the possibility to change the real-time mode of the system
  * with a magic sys request. This helps in debugging in case the system fails