// 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;    
}