-
Notifications
You must be signed in to change notification settings - Fork 0
/
circularQueue.h
160 lines (135 loc) · 3.49 KB
/
circularQueue.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
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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#ifndef CIRCULARQ_H
#define CIRCULARQ_H
#include "headers.h"
typedef struct circularQ
{
int front;
int back;
int size; // maximum capacity of Q
int occupied; // actual number of entries
process **entries;
} circularQ;
// Default intializer
// circularQ circularQueueDefault = {0, 0, 0, 0, NULL};
// A function the returns the next index
int circularQForward(circularQ *queue, int i)
{
return (i + queue->size - 1) % queue->size;
}
void circularQprint(circularQ *queue)
{
int size = queue->occupied;
for (int i = 0; i < size; i++)
{
printf("%d\n", queue->entries[i]->id);
fflush(stdout);
}
}
// A function the returns the previous index
int circularQBackward(circularQ *queue, int i)
{
return (i + 1) % queue->size;
}
// A function that creats a queue for the entries
//-1 for faild attempt and 0 for success
int circularQInit(circularQ *queue, int size)
{
if (!queue || !size)
return -1;
if (queue->entries)
return -1;
queue->size = size;
// calloc for dynamic allocation and intializing all entries with (0)
queue->entries = (process **)calloc(queue->size, sizeof(process *));
return 0;
}
// A function that frees the dynamically allocated memory
//-1 for faild attempt and 0 for success
int circularQFree(circularQ *queue)
{
if (!queue)
return -1;
if (!queue->entries)
return -1;
// free() is to free the memory allocation
free(queue->entries);
return 0;
}
// A function that returns a pointer to the front entry
// returns NULL on failure
process *circularQFront(circularQ *queue)
{
if (!queue)
return NULL;
if (!queue->entries)
return NULL;
// Queue is empty
if (!queue->occupied)
return NULL;
return queue->entries[queue->front];
}
// A function that enqueues and returns a pointer to the new front entry
// returns NULL on failure
int circularQEnqueue(circularQ *queue, process *p)
{
if (!queue)
return -1;
if (!queue->entries)
return -1;
// Queue is full
if (queue->occupied == queue->size)
return -1;
queue->entries[queue->back] = p;
// Move back circularly
queue->back = circularQBackward(queue, queue->back);
queue->occupied = queue->occupied < queue->size ? queue->occupied + 1 : queue->size;
return 0;
}
// A function that dequeues and returns a pointer to the new front entry
// returns NULL on failure
process *circularQDequeue(circularQ *queue)
{
if (!queue)
return NULL;
if (!queue->entries)
return NULL;
// Queue is empty
if (!queue->occupied)
return NULL;
// Remove front element
process *p = queue->entries[queue->front];
// Move back circularly
queue->front = circularQBackward(queue, queue->front);
queue->occupied = queue->occupied ? queue->occupied - 1 : 0;
return p;
}
// A function that removes a process entry
// returns NULL on failure
process *circularQRemove(circularQ *queue, process *p)
{
if (!queue)
return NULL;
if (!queue->entries)
return NULL;
// Queue is empty
if (!queue->occupied)
return NULL;
// Searching for P on step before back
int i = circularQForward(queue, queue->back);
for (; i != queue->back; i = circularQForward(queue, i))
{
if (queue->entries[i] == p)
break;
}
if (i == queue->back)
return NULL;
for (; i != queue->back; i = circularQBackward(queue, i))
{
queue->entries[i] = queue->entries[circularQBackward(queue, i)];
}
// Move forward circularly
queue->back = circularQForward(queue, queue->back);
queue->occupied = queue->occupied ? queue->occupied - 1 : 0;
return p;
}
#endif