Min Heap for Xinu

minHeap.c

// @author Marty Kausas <mkausas@purdue.edu>
// Adapted from http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/Progs/Heap/Basic/delete/Heap.java

// This is a basic min-heap implementation written in C for Xinu. It is quite messy. I suggest using it as a black-box. 

#include <xinu.h>

void printOldReadyList(); 

int rl_node_count = 0;
void testHeap() {

/*
	// test helper functions
	rl_proc p1 = {1, 1};
	rl_proc p2 = {2, 2};
	rl_proc p3 = {3, 3};
	rl_proc p4 = {4, 4};
	rl_proc p5 = {5, 5};
	rl_proc p6 = {6, 6};
	rl_proc p7 = {7, 7};

	put(p5);
	put(p4);
	put(p2);
	put(p1);
	put(p3);
	printHeap();

	int pid = findProcess(5);
	kprintf("\nFound Process at %d\n", pid);

	removeProcess(pid);
	printHeap();

	printLinear();
*/
	

	// test required functions 
	newheap();
	heapinsert(4, 4);
	heapinsert(5, 2);
	heapinsert(6, 6);
	heapinsert(1, 6);
	heapinsert(2, 5);
	heapinsert(3, 3);

	printReadyList();
	printf("\nheapminkey: %d\n", heapminkey());
	printReadyList();
	printf("\nheapgethead: %d\n", heapgethead());
	printReadyList();
	printf("\nheapgetitem: %d\n", heapgetitem(4));
	printReadyList();
	
}

void printReadyList() {
	kprintf("\n--- Ready List len = %d ---\n", rl_node_count);
	
	kprintf("New ReadyList: ");
	int i;
	for (i = 1; i <= rl_node_count; i++) {
		kprintf("[pid=%d key=%d] ", readyList[i].pid, readyList[i].key);	
	}
	kprintf("\n");
	//printOldReadyList();
}

int isReadyListEmpty() {
	return rl_node_count < 1;
}

void printOldReadyList() {
	int16 curr = firstid(readylist);
	int16 tail = queuetail(readylist);
	kprintf("Old ReadyList: ");
	while (curr != tail) {
		kprintf("[pid=%d key=%d] ", curr, queuetab[curr].qkey);
		curr = queuetab[curr].qnext;
	}
	kprintf("\n");
}

// --- Required Methods --- //

// creates the new heap, return OK or SYSERR. 
status newheap() {
	return OK;
} 

// insert a process of PID with the given key into the heap
status heapinsert(pid32 pid, int32 key) {
	//kprintf("Inserting pid: %d key: %d\n", pid, key);
	rl_proc p = { key, pid };
	put(p);
	//printReadyList();
	return OK;
} 

// removes the root node and return its process id.
pid32 heapgethead() {  
	//kprintf("heapgethead called len = %d\n", rl_node_count);
	if (rl_node_count == 0) {
		kprintf("Get head being called while heap is empty\n");
		return 0;
	}
	pid32 removed = removeProcess(1);
	return removed;
	//return getitem(removed);
}

// returns the key value at the root node of the heap without removing the node.
int32 heapminkey() {
	//kprintf("heapminkey: %d\n", readyList[1].key);
	return readyList[1].key;
}



// find and remove the process with the given pid from the heap. Status returns the process id or SYSERR 
pid32 heapgetitem(pid32 pid) {
	int processIndex = findProcess(pid);
	if (processIndex == -1) return SYSERR;
	
	return removeProcess(processIndex);
}


// --- helper functions --- //

/* ============================================================
   put(x): insert x into the heap

   (we must make sure the heap properties are preserved !
   ============================================================ */
void put( rl_proc x )
{
	readyList[rl_node_count+1] = x;        // Insert x in the "fartest left location"
	// This preserves the "complete" bin tree prop

	rl_node_count++;            // We have 1 more node

	HeapFilterUp( rl_node_count ); // Filter the inserted node up
	// This preserves the "min. value at root" prop
}

/* ===============================================================
   HeapFilterUp(k): Filter the node readyList[k] to its proper position
   in the heap
   =============================================================== */
void HeapFilterUp( int k )
{
	int parent;                 /* parent = parent */
	rl_proc help;

	while ( k != 1 )    /* k has a parent node */
	{ /* Parent is not the root */

		parent = k/2;

		if ( RL_KEY(k) < RL_KEY(parent) )
		{ 
			help = readyList[parent];
			readyList[parent] = readyList[k];
			readyList[k] = help;

			/* ===============================
			   Continue filter up one level
			   =============================== */
			k = parent;          // k moved up one level
		}
		else
		{
			break;
		}

	}
}


int findProcess(pid32 pid) {
	int i;
	for (i = 0; i <= rl_node_count; i++) 
		if (readyList[i].pid == pid) 
			return i;

	return -1;
}

pid32 removeProcess(int k)
{
	int    parent;
	rl_proc r;// = {readyList[k].key, readyList[k].pid};             // Variable to hold deleted value

	r = readyList[k];             // Save return value

	readyList[k] = readyList[rl_node_count];     // Replace deleted node with the right most leaf
	// This fixes the "complete bin. tree" property
	rl_node_count--;
	if (rl_node_count < 1) {
		rl_node_count = 0;
		return r.pid; 
	}

	parent = k/2;

	if ( k == 1 /* k is root */ || RL_KEY(parent) < RL_KEY(k) ) 
	{
		//kprintf("\nHeap before filter DOWN:\n");
		//printReadyList();
		//printHeap();
		HeapFilterDown(k);  // Move the node readyList[k] DOWN the tree
	}
	else
	{
		//kprintf("\nHeap before filter UP:\n");
		//printReadyList();
		//printHeap();
		HeapFilterUp(k);    // Move the node readyList[k] UP the tree
	}

	return r.pid;
}

void HeapFilterDown( int k )
{
	int child1, child2;
	rl_proc help;


	while ( 2*k <= rl_node_count )
	{
		child1 = 2*k;                 // Child1 = left  child of k
		child2 = 2*k+1;               // Child2 = right child of k

		if ( child2 <= rl_node_count )
		{
			/* ========================================
			   Node k has 2 children nodes....
			   Find the min. of 3 nodes !!!
			   ======================================== */
			if ( RL_KEY(k) < RL_KEY(child1) && RL_KEY(k) < RL_KEY(child2) )
			{
				/* -------------------------------------------------------
				   Node k is in correct location... It's a heap. Stop... 
				   ------------------------------------------------------- */
				break;
			}
			else 
			{
				/* =========================================
				   Replace readyList[k] with the smaller child node
				   ========================================= */
				if ( RL_KEY(child1) < RL_KEY(child2) )
				{
					/* -------------------------------------------------
					   Child1 is smaller: swap readyList[k] with readyList[child1]
					   ------------------------------------------------- */
					help = readyList[k];
					readyList[k] = readyList[child1];
					readyList[child1] = help;

					k = child1;         // Replacement node is now readyList[child1]
				}
				else
				{
					/* -------------------------------------------------
					   Child2 is smaller: swap readyList[k] with readyList[child2]
					   ------------------------------------------------- */
					help = readyList[k];
					readyList[k] = readyList[child2];
					readyList[child2] = help;

					k = child2;        // Replacement node is now readyList[child2]
				}
			}
		}
		else
		{
			/* ========================================
			   Node k only has a left child node
			   ======================================== */
			if ( RL_KEY(k) < RL_KEY(child1) )
			{
				/* -------------------------------------------------------
				   Node k is in correct location... It's a heap. Stop... 
				   ------------------------------------------------------- */
				break;
			}
			else 
			{
				/* -------------------------------------------------------
				   Child1 is smaller: swap readyList[k] with readyList[child1]
				   ------------------------------------------------------- */
				help = readyList[k];
				readyList[k] = readyList[child1];
				readyList[child1] = help;

				k = child1;         // Replacement node is now readyList[child1]
			}
		}
	}
}



/* ======================================================= */


void printnode(int n, int h)
{
	int i;
	for (i = 0; i < h; i++) {
		printf("        ");
	}

	printf("[ pid:%d key:%d ] \n", readyList[n].pid, readyList[n].key);
}

void printHeap()
{
	if ( rl_node_count == 0 )
	{
		printf("*** heap is empty\n");
		printf("================================\n");
		return;
	}

	showR( 1, 0 );
	printf("================================\n");
}

void showR(int n, int h)
{
	if (n > rl_node_count)
		return;

	showR(2*n+1, h+1);
	printnode(n, h);
	showR(2*n, h+1);
}

minHeap.h

/* minHeap.h */

#define RL_KEY(x) (readyList[x].key)

typedef struct rl_proc {
	int32 key;
	pid32 pid;
} rl_proc;

rl_proc readyList[NPROC];

// Helper functions (not public)
void Heap(int size);
void put(rl_proc x);
void HeapFilterUp( int k );
pid32 removeProcess(int k);
void HeapFilterDown( int k );
void printnode(int n, int h);
void printHeap();
void showR(int n, int h);
int findProcess(pid32 pid);