// Written by Shahir Ahmed and Boosung Kim
#include "../h/pcb.h"
pcb_t* pcbFree_h;
pcb_t pcbFree_table[MAXPROC];
static void initializePCB(pcb_t* pcbNode);
/*
* Function: initPcbs
* --------------------
* Initialize the pcbFree list to contain all the elements of the static array
* of MAXPROC PCBs.
*
*/
void initPcbs()
{
// Sets head pointer to the first PCB
pcbFree_h = &pcbFree_table[0];
for (int i=0; i < MAXPROC - 1; i++) {
pcbFree_table[i].p_next = &pcbFree_table[i+1];
}
// Set last PCB to point to NULL.
pcbFree_table[MAXPROC - 1].p_next = NULL;
}
/*
* Function: freePcb
* --------------------
* Insert the element pointed to by p onto the pcbFree list (whose head is
* pointed to by the variable pcbFree_h)
*
* p: pointer to PCB to be inserted into pcbFree list
*
*/
void freePcb(pcb_t* p)
{
pcb_t* current = pcbFree_h;
if (current == NULL) {
// When pcbFree list is empty
pcbFree_h = p;
pcbFree_h->p_next = NULL;
} else {
// When pcbFree list is not empty
while (current->p_next != NULL) {
current = current->p_next;
}
current->p_next = p;
p->p_next = NULL;
}
}
/*
* Function: allocPcb
* --------------------
* Remove an element from the pcbFree list. For the removed PCB element
* provide initial values for all queue and tree related PCB fields.
*
* returns: A pointer to the removed element
* returns NULL if pcbFree_h NULL (if the pcbFree list is empty)
*/
pcb_t *allocPcb()
{
if (pcbFree_h == NULL) {
return NULL;
}
pcb_t* remove = pcbFree_h;
pcbFree_h = remove->p_next;
initializePCB(remove);
return remove;
}
/*
* Function: initializePCB
* --------------------
* Takes a pointer to PCB and initializes all process queue and tree fields of
* the PCB to NULL.
*
* pcbNode: pointer to the PCB to initialize
*
*/
static void initializePCB(pcb_t* pcbNode) {
pcbNode->p_next = NULL;
pcbNode->p_prev = NULL;
pcbNode->p_prnt = NULL;
pcbNode->p_child = NULL;
pcbNode->p_next_sib = NULL;
pcbNode->p_prev_sib = NULL;
}
/*
* Function: mkEmptyProcQ
* --------------------
* Initializes a variable to be the tail pointer to a process queue.
*
* returns: a pointer to the tail of an empty process queue
*/
pcb_t* mkEmptyProcQ()
{
return NULL;
}
/*
* Function: emptyProcQ
* --------------------
* Return true or false of whether the process queue is empty.
*
* tp: pointer to tail PCB
*
* returns: returns one if the queue is empty
* returns zero otherwise
*/
int emptyProcQ(pcb_t *tp)
{
return (tp == NULL);
}
/*
* Function: insertProcQ
* --------------------
* Insert the PCB pointed to by p into the process queue whose tail pointer
* is pointed to by tp.
*
* tp: pointer to tail pointer to PCB
* p: pointer to a new tail element
*
*/
void insertProcQ(pcb_t** tp, pcb_t* p)
{
if (!emptyProcQ(*tp)) {
// Insert into existing queue
p->p_prev = *tp;
p->p_next = (*tp)->p_next;
(*tp)->p_next->p_prev = p;
(*tp)->p_next = p;
} else {
// Insert into a new queue
p->p_prev = p;
p->p_next = p;
}
*tp = p;
}
/*
* Function: headProcQ
* --------------------
* Return a pointer to the first PCB.
*
* tp: pointer to tail PCB
*
* returns: returns a pointer to the first PCB if the queue is not empty
* returns NULL otherwise
*/
pcb_t *headProcQ(pcb_t *tp)
{
if (emptyProcQ(tp)) {
return NULL;
}
return tp->p_next;
}
/*
* Function: removeProcQ
* --------------------
* Removes the first PCB element from the process queue.
*
* tp: pointer to tail pointer of PCB
*
* returns: returns pointer to the removed element
* returns NULL otherwise
*/
pcb_t* removeProcQ(pcb_t **tp)
{
if (emptyProcQ(*tp)) {
// When the queue is empty
return NULL;
}
if ((*tp)->p_prev == *tp) {
// When the queue has only one element
pcb_t *removedPCB = *tp;
*tp = NULL;
return removedPCB;
}
pcb_t *head = (*tp)->p_next;
(*tp)->p_next = head->p_next;
head->p_next->p_prev = *tp;
return head;
}
/*
* Function: outProcQ
* --------------------
* Remove PCB pointed to by p from the process queue whose tail pointer
* is pointed to by tp.
*
* tp: pointer to tail pointer of PCB
* p: pointer to PCB to remove from queue
*
* returns: returns p if p exists in indicated queue
* returns NULL otherwise
*/
pcb_t* outProcQ(pcb_t **tp, pcb_t *p)
{
if (emptyProcQ(*tp)) {
// When queue is empty
return NULL;
} else if (*tp == p) {
// When p is the tail element
if (p->p_prev != *tp) {
// When p is not the only element
*tp = p->p_prev;
(*tp)->p_next = p->p_next;
p->p_next->p_prev = *tp;
} else {
// when p is the only element
*tp = NULL;
}
return p;
} else {
// When p is not the tail element
pcb_t* current = *tp;
do {
if (current == p) {
current->p_prev->p_next = current->p_next;
current->p_next->p_prev = current->p_prev;
return p;
}
current = current->p_prev;
} while (current != *tp);
return NULL;
}
}
/*
* Function: emptyChild
* --------------------
* Returns whether or not p has any children.
*
* p: pointer to PCB
*
* returns: returns 1 if the PCB pointed to by p has no children
* returns 0 otherwise
*/
int emptyChild(pcb_t *p)
{
return p->p_child == NULL;
}
/*
* Function: insertChild
* --------------------
* Make the PCB pointed to by p the first child of the PCB
* pointed to by prnt.
*
* prnt: pointer to parent PCB
* p: pointer to PCB to child
*
*/
void insertChild(pcb_t *prnt, pcb_t *p)
{
if (prnt->p_child == NULL){
// Parent PCB has no children
prnt->p_child = p;
p->p_prnt = prnt;
return;
}
// Parent PCB has children
p->p_prnt = prnt;
p->p_next_sib = prnt->p_child;
prnt->p_child->p_prev_sib = p;
prnt->p_child = p;
}
/*
* Function: removeChild
* --------------------
* Make the first child of the PCB pointed to by p no longer
* a child of p.
*
* p: pointer to PCB
*
* returns: returns first child PCB of p if p has children
* returns NULL otherwise
*/
pcb_t* removeChild(pcb_t *p)
{
pcb_t* removed = p->p_child;
if(p->p_child == NULL){
// p has no children
return NULL;
}
if(p->p_child->p_next_sib == NULL){
// p's first child has no next sibling
p->p_child->p_prnt = NULL;
p->p_child = NULL;
} else {
// p's first child has a next sibling
p->p_child->p_prnt = NULL;
p->p_child->p_next_sib->p_prev_sib = NULL;
p->p_child = p->p_child->p_next_sib;
}
return removed;
}
/*
* Function: outChild
* --------------------
* Make the PCB pointed to by p no longer the child of its
* parent.
*
* p: pointer to PCB
*
* returns: returns p if p has a parent
* returns NULL otherwise
*/
pcb_t *outChild(pcb_t* p)
{
if(p->p_prnt == NULL){
// p has no parent
return NULL;
}
if(p->p_prev_sib == NULL){
// p does not have a previous sibling
removeChild(p->p_prnt);
} else {
// p has a previous sibling
if(p->p_next_sib == NULL){
// p has no next sibling
p->p_prnt = NULL;
p->p_prev_sib->p_next_sib = NULL;
p->p_prev_sib = NULL;
} else {
// p has a next sibling
p->p_prnt = NULL;
p->p_prev_sib->p_next_sib = p->p_next_sib;
p->p_next_sib->p_prev_sib = p->p_prev_sib;
}
p->p_prev_sib = NULL;
p->p_next_sib = NULL;
}
return p;
}