Kernel/Queue.h


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

#pragma once

#include "types.h"

template<typename T>
class Queue {
public:
    struct Node {
        explicit Node(T&& value)
            : value(move(value))
        { }

        Node* next { nullptr };
        Node* prev { nullptr };
        T value;
    };

    Queue() { }
    ~Queue()
    {
        while (!is_empty())
            dequeue();
    }

    bool is_empty() const { return !m_head; }
    void enqueue(T&& item)
    {
        auto* new_node = new Node(move(item));
        if (!m_head) {
            m_head = new_node;
            m_tail = new_node;
        } else if (m_tail) {
            new_node->prev = m_tail;
            m_tail->next = new_node;
            m_tail = new_node;
        }
        dump("enqueue");
    }

    T dequeue()
    {
        ASSERT(m_head);
        T value = move(m_head->value);
        auto* oldHead = m_head;
        if (oldHead->next) {
            oldHead->next->prev = nullptr;
            m_head = oldHead->next;
        } else {
            m_head = nullptr;
        }
        if (m_tail == oldHead)
            m_tail = nullptr;
        delete oldHead;
        dump("dequeue");
        //asm volatile("cli;hlt");
        return value;
    }

    Node* head() { return m_head; }

    T take(Node& node)
    {
        T value = move(node.value);
        if (node.prev) {
            node.prev->next = node.next;
        } else {
            m_head = node.next;
        }
        if (node.next) {
            node.next->prev = node.prev;
        } else {
            m_tail = node.prev;
        }
        delete &node;
        dump("take");
        return value;
    }

private:
    void dump(const char* op)
    {
        return;
        asm volatile("cli");
        ASSERT(m_head != (void*)0xaaaaaaaa);
        ASSERT(m_tail != (void*)0xaaaaaaaa);
        kprintf("Queue %p after %s: {m_head=%p, m_tail=%p}\n", this, op, m_head, m_tail);
        for (auto* node = m_head; node; node = node->next) {
            kprintf("  Queue::Node %p%s%s next=%p prev=%p\n", node, node == m_head ? " (head)" : "", node == m_tail ? " (tail)" : "", node->next, node->prev);
        }
        asm volatile("sti");
    }

    Node* m_head { nullptr };
    Node* m_tail { nullptr };
};