Project2/priority_queue.h at main · cs342-OS-project/Project2 · GitHub

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#ifndef PRIORITY_QUEUE
#define PRIORITY_QUEUE

#include "pcb.h"

// DECLARATIONS

struct priority_queue
{
    int currentSize;
    int maxSize;
    struct Process_Control_Block *heap;
};

void init_queue(struct priority_queue *queue, int maxSize);

void heapRebuild(struct priority_queue *queue, int root);

void insert_pcb(struct priority_queue *queue, struct Process_Control_Block pcb);

void delete_pcb(struct priority_queue *queue);

void free_queue(struct priority_queue *queue);

int isFull(struct priority_queue *queue);

struct Process_Control_Block get_min_pcb(struct priority_queue *queue);

void printQueue(struct priority_queue *queue);

// IMPLEMETATION

void init_queue(struct priority_queue *queue, int maxSize)
{
    queue->currentSize = 0;
    queue->maxSize = maxSize;
    queue->heap = malloc(sizeof(struct Process_Control_Block) * maxSize);
}

void heapRebuild(struct priority_queue *queue, int root)
{
    int child = 2 * root + 1;

    if (child < queue->currentSize)
    {
        int rightChild = child + 1;

        if (rightChild < queue->currentSize && queue->heap[rightChild].virtual_runtime < queue->heap[child].virtual_runtime)
        {
            child = rightChild;
        }

        if (queue->heap[root].virtual_runtime > queue->heap[child].virtual_runtime)
        {
            struct Process_Control_Block temp = queue->heap[root];
            queue->heap[root] = queue->heap[child];
            queue->heap[child] = temp;

            heapRebuild(queue, child);
        }
    }
}

void insert_pcb(struct priority_queue *queue, struct Process_Control_Block pcb)
{
    if (queue->currentSize >= queue->maxSize)
    {
        return;
    }

    queue->heap[queue->currentSize] = pcb;

    int place = queue->currentSize;
    int parent = (place - 1) / 2;

    while ( (place > 0) && (queue->heap[place].virtual_runtime <= queue->heap[parent].virtual_runtime))
    {
        struct Process_Control_Block temp = queue->heap[parent];
        queue->heap[parent] = queue->heap[place];
        queue->heap[place] = temp;

        place = parent;
        parent = (place - 1) / 2;
    }
    queue->currentSize++;
}

void delete_pcb(struct priority_queue *queue)
{
    if (queue->currentSize <= 0)
    {
        return;
    }

    queue->currentSize--;
    queue->heap[0] = queue->heap[queue->currentSize];
    heapRebuild(queue, 0);
}

struct Process_Control_Block get_min_pcb(struct priority_queue *queue)
{
    return queue->heap[0];
}

void free_queue(struct priority_queue *queue)
{
    free(queue->heap);
}

int isFull(struct priority_queue *queue)
{
    if(queue->currentSize == queue->maxSize)
        return 1;
    else
        return 0;
}

void printQueue(struct priority_queue *queue)
{
    int size = queue->currentSize;
    printf("RUNQUEUE: ");

    for (int i = 0; i < size; i++)
    {
        printf("%d ", queue->heap[i].pid);
    }
    printf("\n");
}

#endif