6 files changed, 228 insertions, 3 deletions

diff --git a/src/common/common.vcxproj b/src/common/common.vcxproj
index 5dc6ff790..86295a480 100644
--- a/src/common/common.vcxproj
+++ b/src/common/common.vcxproj
@@ -190,6 +190,7 @@
     <ClInclude Include="swap.h" />
     <ClInclude Include="symbols.h" />
     <ClInclude Include="thread.h" />
+    <ClInclude Include="thread_queue_list.h" />
     <ClInclude Include="thunk.h" />
     <ClInclude Include="timer.h" />
     <ClInclude Include="utf8.h" />
diff --git a/src/common/common.vcxproj.filters b/src/common/common.vcxproj.filters
index 268730228..84cfa8837 100644
--- a/src/common/common.vcxproj.filters
+++ b/src/common/common.vcxproj.filters
@@ -40,6 +40,7 @@
     <ClInclude Include="symbols.h" />
     <ClInclude Include="scm_rev.h" />
     <ClInclude Include="bit_field.h" />
+    <ClInclude Include="thread_queue_list.h" />
   </ItemGroup>
   <ItemGroup>
     <ClCompile Include="break_points.cpp" />
diff --git a/src/common/common_funcs.h b/src/common/common_funcs.h
index f8d10eb3e..dca4dc47f 100644
--- a/src/common/common_funcs.h
+++ b/src/common/common_funcs.h
@@ -22,6 +22,11 @@ template<> struct CompileTimeAssert<true> {};
 #define b32(x)  (b16(x) | (b16(x) >>16) )
 #define ROUND_UP_POW2(x)    (b32(x - 1) + 1)
 
+#define MIN(a, b)   ((a)<(b)?(a):(b))
+#define MAX(a, b)   ((a)>(b)?(a):(b))
+
+#define CLAMP(x, min, max)  (((x) > max) ? max : (((x) < min) ? min : (x)))
+
 #define ARRAY_SIZE(a) (sizeof(a) / sizeof(a[0]))
 
 #ifndef _WIN32
diff --git a/src/common/log.h b/src/common/log.h
index d95f51f56..8b39b03a1 100644
--- a/src/common/log.h
+++ b/src/common/log.h
@@ -5,6 +5,8 @@
 #ifndef _LOG_H_
 #define _LOG_H_
 
+#define LOGGING
+
 #define    NOTICE_LEVEL  1  // VERY important information that is NOT errors. Like startup and OSReports.
 #define    ERROR_LEVEL   2  // Critical errors 
 #define    WARNING_LEVEL 3  // Something is suspicious.
@@ -53,7 +55,7 @@ enum LOG_TYPE {
     WII_IPC_ES,
     WII_IPC_FILEIO,
     WII_IPC_HID,
-    WII_IPC_HLE,
+    KERNEL,
     SVC,
     NDMA,
     HLE,
diff --git a/src/common/log_manager.cpp b/src/common/log_manager.cpp
index 80fd473b9..146472888 100644
--- a/src/common/log_manager.cpp
+++ b/src/common/log_manager.cpp
@@ -60,13 +60,13 @@ LogManager::LogManager()
     m_Log[LogTypes::LOADER]             = new LogContainer("Loader",            "Loader");
     m_Log[LogTypes::FILESYS]            = new LogContainer("FileSys",           "File System");
     m_Log[LogTypes::WII_IPC_HID]        = new LogContainer("WII_IPC_HID",       "WII IPC HID");
-    m_Log[LogTypes::WII_IPC_HLE]        = new LogContainer("WII_IPC_HLE",       "WII IPC HLE");
+    m_Log[LogTypes::KERNEL]             = new LogContainer("KERNEL",            "KERNEL HLE");
     m_Log[LogTypes::WII_IPC_DVD]        = new LogContainer("WII_IPC_DVD",       "WII IPC DVD");
     m_Log[LogTypes::WII_IPC_ES]         = new LogContainer("WII_IPC_ES",        "WII IPC ES");
     m_Log[LogTypes::WII_IPC_FILEIO]     = new LogContainer("WII_IPC_FILEIO",    "WII IPC FILEIO");
     m_Log[LogTypes::RENDER]             = new LogContainer("RENDER",            "RENDER");
     m_Log[LogTypes::LCD]                = new LogContainer("LCD",               "LCD");
-    m_Log[LogTypes::SVC]                = new LogContainer("SVC",               "Supervisor Call");
+    m_Log[LogTypes::SVC]                = new LogContainer("SVC",               "Supervisor Call HLE");
     m_Log[LogTypes::NDMA]               = new LogContainer("NDMA",              "NDMA");
     m_Log[LogTypes::HLE]                = new LogContainer("HLE",               "High Level Emulation");
     m_Log[LogTypes::HW]                 = new LogContainer("HW",                "Hardware");
diff --git a/src/common/thread_queue_list.h b/src/common/thread_queue_list.h
new file mode 100644
index 000000000..4a89572f6
--- /dev/null
+++ b/src/common/thread_queue_list.h
@@ -0,0 +1,216 @@
+// Copyright 2014 Citra Emulator Project / PPSSPP Project
+// Licensed under GPLv2
+// Refer to the license.txt file included.  
+
+#pragma once
+
+#include "common/common.h"
+
+namespace Common {
+
+template<class IdType>
+struct ThreadQueueList {
+    // Number of queues (number of priority levels starting at 0.)
+    static const int NUM_QUEUES = 128;
+    
+    // Initial number of threads a single queue can handle.
+    static const int INITIAL_CAPACITY = 32;
+
+    struct Queue {
+        // Next ever-been-used queue (worse priority.)
+        Queue *next;
+        // First valid item in data.
+        int first;
+        // One after last valid item in data.
+        int end;
+        // A too-large array with room on the front and end.
+        IdType *data;
+        // Size of data array.
+        int capacity;
+    };
+
+    ThreadQueueList() {
+        memset(queues, 0, sizeof(queues));
+        first = invalid();
+    }
+
+    ~ThreadQueueList() {
+        for (int i = 0; i < NUM_QUEUES; ++i)
+        {
+            if (queues[i].data != NULL)
+                free(queues[i].data);
+        }
+    }
+
+    // Only for debugging, returns priority level.
+    int contains(const IdType uid) {
+        for (int i = 0; i < NUM_QUEUES; ++i)
+        {
+            if (queues[i].data == NULL)
+                continue;
+
+            Queue *cur = &queues[i];
+            for (int j = cur->first; j < cur->end; ++j)
+            {
+                if (cur->data[j] == uid)
+                    return i;
+            }
+        }
+
+        return -1;
+    }
+
+    inline IdType pop_first() {
+        Queue *cur = first;
+        while (cur != invalid())
+        {
+            if (cur->end - cur->first > 0)
+                return cur->data[cur->first++];
+            cur = cur->next;
+        }
+
+        //_dbg_assert_msg_(SCEKERNEL, false, "ThreadQueueList should not be empty.");
+        return 0;
+    }
+
+    inline IdType pop_first_better(u32 priority) {
+        Queue *cur = first;
+        Queue *stop = &queues[priority];
+        while (cur < stop)
+        {
+            if (cur->end - cur->first > 0)
+                return cur->data[cur->first++];
+            cur = cur->next;
+        }
+
+        return 0;
+    }
+
+    inline void push_front(u32 priority, const IdType threadID) {
+        Queue *cur = &queues[priority];
+        cur->data[--cur->first] = threadID;
+        if (cur->first == 0)
+            rebalance(priority);
+    }
+
+    inline void push_back(u32 priority, const IdType threadID) {
+        Queue *cur = &queues[priority];
+        cur->data[cur->end++] = threadID;
+        if (cur->end == cur->capacity)
+            rebalance(priority);
+    }
+
+    inline void remove(u32 priority, const IdType threadID) {
+        Queue *cur = &queues[priority];
+        //_dbg_assert_msg_(SCEKERNEL, cur->next != NULL, "ThreadQueueList::Queue should already be linked up.");
+
+        for (int i = cur->first; i < cur->end; ++i)
+        {
+            if (cur->data[i] == threadID)
+            {
+                int remaining = --cur->end - i;
+                if (remaining > 0)
+                    memmove(&cur->data[i], &cur->data[i + 1], remaining * sizeof(IdType));
+                return;
+            }
+        }
+
+        // Wasn't there.
+    }
+
+    inline void rotate(u32 priority) {
+        Queue *cur = &queues[priority];
+        //_dbg_assert_msg_(SCEKERNEL, cur->next != NULL, "ThreadQueueList::Queue should already be linked up.");
+
+        if (cur->end - cur->first > 1)
+        {
+            cur->data[cur->end++] = cur->data[cur->first++];
+            if (cur->end == cur->capacity)
+                rebalance(priority);
+        }
+    }
+
+    inline void clear() {
+        for (int i = 0; i < NUM_QUEUES; ++i)
+        {
+            if (queues[i].data != NULL)
+                free(queues[i].data);
+        }
+        memset(queues, 0, sizeof(queues));
+        first = invalid();
+    }
+
+    inline bool empty(u32 priority) const {
+        const Queue *cur = &queues[priority];
+        return cur->first == cur->end;
+    }
+
+    inline void prepare(u32 priority) {
+        Queue *cur = &queues[priority];
+        if (cur->next == NULL)
+            link(priority, INITIAL_CAPACITY);
+    }
+
+private:
+    Queue *invalid() const {
+        return (Queue *) -1;
+    }
+
+    void link(u32 priority, int size) {
+        //_dbg_assert_msg_(SCEKERNEL, queues[priority].data == NULL, "ThreadQueueList::Queue should only be initialized once.");
+
+        if (size <= INITIAL_CAPACITY)
+            size = INITIAL_CAPACITY;
+        else
+        {
+            int goal = size;
+            size = INITIAL_CAPACITY;
+            while (size < goal)
+                size *= 2;
+        }
+        Queue *cur = &queues[priority];
+        cur->data = (IdType *) malloc(sizeof(IdType) * size);
+        cur->capacity = size;
+        cur->first = size / 2;
+        cur->end = size / 2;
+
+        for (int i = (int) priority - 1; i >= 0; --i)
+        {
+            if (queues[i].next != NULL)
+            {
+                cur->next = queues[i].next;
+                queues[i].next = cur;
+                return;
+            }
+        }
+
+        cur->next = first;
+        first = cur;
+    }
+
+    void rebalance(u32 priority) {
+        Queue *cur = &queues[priority];
+        int size = cur->end - cur->first;
+        if (size >= cur->capacity - 2)  {
+            IdType *new_data = (IdType *)realloc(cur->data, cur->capacity * 2 * sizeof(IdType));
+            if (new_data != NULL)  {
+                cur->capacity *= 2;
+                cur->data = new_data;
+            }
+        }
+
+        int newFirst = (cur->capacity - size) / 2;
+        if (newFirst != cur->first) {
+            memmove(&cur->data[newFirst], &cur->data[cur->first], size * sizeof(IdType));
+            cur->first = newFirst;
+            cur->end = newFirst + size;
+        }
+    }
+
+    // The first queue that's ever been used.
+    Queue *first;
+    // The priority level queues of thread ids.
+    Queue queues[NUM_QUEUES];
+};
+
+} // namespace