1 files changed, 304 insertions, 0 deletions
diff --git a/kernel.soso/list.c b/kernel.soso/list.c
new file mode 100644
index 00000000..09883eba
--- /dev/null
+++ b/kernel.soso/list.c
@@ -0,0 +1,304 @@
+#include "alloc.h"
+#include "common.h"
+#include "list.h"
+
+List* List_Create()
+{
+    List* list = (List*)kmalloc(sizeof(List));
+
+    memset((uint8*)list, 0, sizeof(List));
+
+    return list;
+}
+
+void List_Clear(List* list)
+{
+    ListNode* listNode = list->head;
+
+    while (NULL != listNode)
+    {
+        ListNode* next = listNode->next;
+
+        kfree(listNode);
+
+        listNode = next;
+    }
+
+    list->head = NULL;
+    list->tail = NULL;
+}
+
+void List_Destroy(List* list)
+{
+    List_Clear(list);
+
+    kfree(list);
+}
+
+List* List_CreateClone(List* list)
+{
+    List* newList = List_Create();
+
+    List_Foreach(n, list)
+    {
+        List_Append(newList, n->data);
+    }
+
+    return newList;
+}
+
+BOOL List_IsEmpty(List* list)
+{
+    //At empty state, both head and tail are null!
+    return list->head == NULL;
+}
+
+void List_Append(List* list, void* data)
+{
+    ListNode* node = (ListNode*)kmalloc(sizeof(ListNode));
+
+    memset((uint8*)node, 0, sizeof(ListNode));
+    node->data = data;
+
+    //At empty state, both head and tail are null!
+    if (NULL == list->tail)
+    {
+        list->head = node;
+
+        list->tail = node;
+
+        return;
+    }
+
+    node->previous = list->tail;
+    node->previous->next = node;
+    list->tail = node;
+}
+
+void List_Prepend(List* list, void* data)
+{
+    ListNode* node = (ListNode*)kmalloc(sizeof(ListNode));
+
+    memset((uint8*)node, 0, sizeof(ListNode));
+    node->data = data;
+
+    //At empty state, both head and tail are null!
+    if (NULL == list->tail)
+    {
+        list->head = node;
+
+        list->tail = node;
+
+        return;
+    }
+
+    node->next = list->head;
+    node->next->previous = node;
+    list->head = node;
+}
+
+ListNode* List_GetFirstNode(List* list)
+{
+    return list->head;
+}
+
+ListNode* List_GetLastNode(List* list)
+{
+    return list->tail;
+}
+
+ListNode* List_FindFirstOccurrence(List* list, void* data)
+{
+    List_Foreach(n, list)
+    {
+        if (n->data == data)
+        {
+            return n;
+        }
+    }
+
+    return NULL;
+}
+
+int List_FindFirstOccurrenceIndex(List* list, void* data)
+{
+    int result = 0;
+
+    List_Foreach(n, list)
+    {
+        if (n->data == data)
+        {
+            return result;
+        }
+
+        ++result;
+    }
+
+    return -1;
+}
+
+int List_GetCount(List* list)
+{
+    int result = 0;
+
+    List_Foreach(n, list)
+    {
+        ++result;
+    }
+
+    return result;
+}
+
+void List_RemoveNode(List* list, ListNode* node)
+{
+    if (NULL == node)
+    {
+        return;
+    }
+
+    if (NULL != node->previous)
+    {
+        node->previous->next = node->next;
+    }
+
+    if (NULL != node->next)
+    {
+        node->next->previous = node->previous;
+    }
+
+    if (node == list->head)
+    {
+        list->head = node->next;
+    }
+
+    if (node == list->tail)
+    {
+        list->tail = node->previous;
+    }
+
+    kfree(node);
+}
+
+void List_RemoveFirstNode(List* list)
+{
+    if (NULL != list->head)
+    {
+        List_RemoveNode(list, list->head);
+    }
+}
+
+void List_RemoveLastNode(List* list)
+{
+    if (NULL != list->tail)
+    {
+        List_RemoveNode(list, list->tail);
+    }
+}
+
+void List_RemoveFirstOccurrence(List* list, void* data)
+{
+    ListNode* node = List_FindFirstOccurrence(list, data);
+
+    if (NULL != node)
+    {
+        List_RemoveNode(list, node);
+    }
+}
+
+Stack* Stack_Create()
+{
+    Stack* stack = (Stack*)kmalloc(sizeof(Stack));
+
+    memset((uint8*)stack, 0, sizeof(Stack));
+
+    stack->list = List_Create();
+
+    return stack;
+}
+
+void Stack_Clear(Stack* stack)
+{
+    List_Clear(stack->list);
+}
+
+void Stack_Destroy(Stack* stack)
+{
+    List_Destroy(stack->list);
+
+    kfree(stack);
+}
+
+BOOL Stack_IsEmpty(Stack* stack)
+{
+    return List_IsEmpty(stack->list);
+}
+
+void Stack_Push(Stack* stack, void* data)
+{
+    List_Prepend(stack->list, data);
+}
+
+void* Stack_Pop(Stack* stack)
+{
+    void* result = NULL;
+
+    ListNode* node = List_GetFirstNode(stack->list);
+
+    if (NULL != node)
+    {
+        result = node->data;
+
+        List_RemoveNode(stack->list, node);
+    }
+
+    return result;
+}
+
+Queue* Queue_Create()
+{
+    Queue* queue = (Queue*)kmalloc(sizeof(Queue));
+
+    memset((uint8*)queue, 0, sizeof(Queue));
+
+    queue->list = List_Create();
+
+    return queue;
+}
+
+void Queue_Clear(Queue* queue)
+{
+    List_Clear(queue->list);
+}
+
+void Queue_Destroy(Queue* queue)
+{
+    List_Destroy(queue->list);
+
+    kfree(queue);
+}
+
+BOOL Queue_IsEmpty(Queue* queue)
+{
+    return List_IsEmpty(queue->list);
+}
+
+void Queue_Enqueue(Queue* queue, void* data)
+{
+    List_Append(queue->list, data);
+}
+
+void* Queue_Dequeue(Queue* stack)
+{
+    void* result = NULL;
+
+    ListNode* node = List_GetFirstNode(stack->list);
+
+    if (NULL != node)
+    {
+        result = node->data;
+
+        List_RemoveNode(stack->list, node);
+    }
+
+    return result;
+}