/*
                   This code implements a priority queue as a heap. Each node of the
                   heap has an identifier (id) as well as a priority. insertIntoHeap()
                   is used to add a node to the heap. extractFromHeap() is used to
                   extract the node with the highest priority from the heap and return
                   its identifier. whoIsOnTopOfHeap() simply returns the identifier of 
                   this node, without afecting the heap. deleteFromHeap() is used to 
                   remove an arbitrary node from the heap. (See further comments for 
                   each individual function.) The variable "heapsize" is the number 
                   of nodes in the heap at any given moment. 

                   getPriority() can be used to check the priority of a node, and
                   setPriority() can be used to change the priority, which will cause 
                   the heap to be reconfigured. Also, a "wait counter" has been added 
                   to each node. This counts the number of nodes that have been removed 
                   from the queue since the given node was inserted. The function 
                   getWaitCounter() can be used to obtain this value. The function 
                   bumpAllPriorities() can be used to change all priorities by a certain 
                   amount. These four utility functions (or a subset of them) can be 
                   used to implement a dynamic priority policy to avoid starvation. 
                 */


                 /* Should the main() function, which is just test code, be included? */

             #define INCLUDE_HEAP_TEST_CODE


                 /* Should heapsize be defined here (or is it defined elsewhere)? */

             #define HEAPSIZE_DEFINED_LOCALLY


                 /* Are we compiling as part of the Minix kernel? */
        /*
             #define USING_HEAP_IN_MINIX_KERNEL
        */

                 /* If so, should node identifiers really be pointers to proc structures? */
        /*
             #define PTR_TO_PROC_TABLE_MODE
        */

                 /*
                   If more than one process has the highest priority and if the constant
                   TRY_TO_BE_FAIR_WHEN_EQUAL_PRIORITIES is defined, then it will "try" to 
                   extract the one added first to the heap. 
                 */
        /*
             #define TRY_TO_BE_FAIR_WHEN_EQUAL_PRIORITIES
        */

                 /* Are we dubugging in a stand alone environment? */
        /*
             #define DEBUG_OUTSIDE_OF_MINIX
        */

                 /* Are we debugging as part of the Minix kernel? */
        /*
             #define DEBUG_HEAP_IN_MINIX
        */


             #ifdef INCLUDE_HEAP_TEST_CODE
                #include<stdio.h>
             #endif

             #define MAX_NODES 100

             #ifdef HEAPSIZE_DEFINED_LOCALLY
                    int heapsize = 0;
             #endif

                 /* 
                   Corresponding triples of entries from the following three arrays constitute 
                   a single entry ("node") in a priority queue, implemented as a heap.
                 */ 
             #ifdef PTR_TO_PROC_TABLE_MODE
                 struct proc *id_array[MAX_NODES];
             #else
                 int id_array[MAX_NODES];
             #endif
                 int priority_array[MAX_NODES];
                 int wait_counter_array[MAX_NODES];



             #ifdef USING_HEAP_IN_MINIX_KERNEL
                  /* 
                    This next function is not part of the heap stuff really, and is 
                    mainly here to test my theory about p_nr in the proc table in Minix.
                  */
                    int proc_pid(p)
                    struct proc *p;
                    {
                      int i;
                      if (p == NIL_PROC) 
                      {
             #ifdef DEBUG_HEAP_IN_MINIX
                        putk('!');
             #endif
                        return -1;
                      }
                      for (i = 0; i < NR_PROCS; i++) 
                        if (p == pproc_addr[NR_TASKS+i]) 
                        {
             #ifdef DEBUG_HEAP_IN_MINIX
                          if (i != p->p_nr) putk('@');
                          if (proc_addr(i) != p) putk('&');
             #endif
                          return i;
                        }
             #ifdef DEBUG_HEAP_IN_MINIX
                      putk('?');
             #endif
                      return -1;
                    }    
             #endif


             #ifndef PTR_TO_PROC_TABLE_MODE
                 /* Display heap */
                 void showHeap(char c)
                 {
                   int i;
                   printf("%c ",c);
                   for (i=0; i < heapsize; i++) printf("%d ", id_array[i]);
                   printf("\n ");
                   for (i=0; i < heapsize; i++) printf("%d ", priority_array[i]);
                   printf("\n");
                 }
             #endif

                 /* Switch two nodes in the heap */
                 void swapInHeap(i, j)
                 int i;
                 int j;
                 {
             #ifdef PTR_TO_PROC_TABLE_MODE
                   struct proc *temp1;
             #else 
                   int temp1;
             #endif
                   int temp2;
                   temp1 = id_array[i];
                   id_array[i] = id_array[j];
                   id_array[j] = temp1;
                   temp2 = priority_array[i];
                   priority_array[i] = priority_array[j];
                   priority_array[j] = temp2;
                   temp2 = wait_counter_array[i];
                   wait_counter_array[i] = wait_counter_array[j];
                   wait_counter_array[j] = temp2;
                 }


                 /* Heapify from the bottom up */
                 void heapifyUp()
                 {
                   int n, parent;
                   n = heapsize - 1;
                   while (n > 0) {
                     parent = (n-1)/2;
                     if (priority_array[parent] >= priority_array[n]) break;
             #ifdef TRY_TO_BE_FAIR_WHEN_EQUAL_PRIORITIES
                     if (parent % 2 == 1 &&
                      priority_array[parent] == priority_array[parent+1]) 
                       swapInHeap(parent,parent+1);
             #endif
                     swapInHeap(n,parent);
             #ifdef TRY_TO_BE_FAIR_WHEN_EQUAL_PRIORITIES
                     if (parent % 2 == 1 && 
                      priority_array[parent] == priority_array[parent+1])
                       swapInHeap(parent,parent+1);
             #endif
                     n = parent;
             #ifdef DEBUG_OUTSIDE_OF_MINIX
                       showHeap('.');
             #endif
                       }
                 }


                 /* Add a node to the heap */
                 void insertIntoHeap(id, priority)
             #ifdef PTR_TO_PROC_TABLE_MODE
                 struct proc *id;
             #else
                 int id;
             #endif
                 int priority;
                 {
                   id_array[heapsize] = id;
                   priority_array[heapsize] = priority;
                   wait_counter_array[heapsize++] = 0;
                   heapifyUp();
             #ifdef DEBUG_HEAP_IN_MINIX
                   putk('(');
                   putk('+');
                   putk('0'+heapsize);
                   putk('0'+proc_pid(id));
                   putk(')');
             #endif
             #ifdef DEBUG_OUTSIDE_OF_MINIX
                       showHeap('^');
             #endif
                 }


                 /* Recursively heapify downwards from index n */
                 void heapifyDown(n)
                 int n;
                 {
                   int left, right, bigger;
                   bigger = left = 2*n + 1;
                   right = 2*n + 2;
                   if (left >= heapsize) return;
                    else if (right < heapsize &&
                     priority_array[left] < priority_array[right])
                      bigger = right;
                   if (priority_array[n] < priority_array[bigger]) {
                     swapInHeap(n,bigger);
             #ifdef TRY_TO_BE_FAIR_WHEN_EQUAL_PRIORITIES
                     if (bigger == right &&
                      priority_array[left] == priority_array[right])
                       swapInHeap(left,right);
                     if (n % 2 == 1 && priority_array[n] == priority_array[n+1]) 
                       swapInHeap(n,n+1);
             #endif
             #ifdef DEBUG_OUTSIDE_OF_MINIX
                   showHeap('.');
             #endif
                   heapifyDown(bigger);
                   }
             #ifdef DEBUG_OUTSIDE_OF_MINIX
                   showHeap('V');
             #endif
                 }


                 /* 
                   Return id of node at top of heap (highest priority) 
                   or -1 or NIL_PROC if empty.
                 */
             #ifdef PTR_TO_PROC_TABLE_MODE
                 struct proc *whoIsOnTopOfHeap()
                 {
                   if (heapsize > 0) return id_array[0]; else return NIL_PROC;
                 }
             #else 
                 int whoIsOnTopOfHeap()
                 {
                   if (heapsize > 0) return id_array[0]; else return -1;
                 }
             #endif


                 /* 
                   Extract the top node of the heap (highest priority) and return
                   the id for this node. Also, increment all counters. If heap is
                   empty, return -1 or NIL_PROC.
                 */
             #ifdef PTR_TO_PROC_TABLE_MODE
                 struct proc *extractFromTopOfHeap() 
             #else
                 int extractFromTopOfHeap() 
             #endif
                 {
                   int i;
             #ifdef PTR_TO_PROC_TABLE_MODE
                   if (heapsize == 0) return NIL_PROC;
             #else
                   if (heapsize == 0) return -1;
             #endif
                   for (i=0; i < heapsize; i++) wait_counter_array[i]++;
                   swapInHeap(0,--heapsize);
                   heapifyDown(0);
             #ifdef DEBUG_HEAP_IN_MINIX
                   putk('(');
                   putk('^');
                   putk('0'+heapsize);
                   putk('0'+proc_pid(id_array[heapsize]));
                   putk(')');
             #endif
                   return id_array[heapsize];
                 }


                 /* Delete specified node and reheapify. Return -1 if not found. */
                 int deleteFromHeap(id)
             #ifdef PTR_TO_PROC_TABLE_MODE
                 struct proc *id; 
             #else 
                 int id;
             #endif
                 {
                   int i, hold_heapsize;
                   for (i=0; i < heapsize; i++) 
                     if (id == id_array[i]) break;
                   if (i == heapsize) return -1;
                   if (i == 0) {
                     swapInHeap(0,--heapsize);
                     heapifyDown(0);
                   } else {
                     swapInHeap(i,--heapsize);
                     hold_heapsize = heapsize;
                     for (heapsize = 2; heapsize <= hold_heapsize; heapsize++)
                       heapifyUp();
                     heapsize = hold_heapsize;
                   }
             #ifdef DEBUG_HEAP_IN_MINIX
                   putk('(');
                   putk('-');
                   putk('0'+heapsize);
                   putk('0'+proc_pid(id));
                   putk(')');
             #endif
                   return 0;
                 }

                 /* Return size of heap */
                 int getHeapsize()
                 {
                   return heapsize;
                 }


                 /* Find wait count for node with given id. Return -1 if not found. */
                 int getWaitCount(id)
             #ifdef PTR_TO_PROC_TABLE_MODE
                 struct proc *id;
             #else
                 int id;
             #endif
                 {
                   int i;
                   for (i=0; i < heapsize; i++) 
                     if (id == id_array[i]) return wait_counter_array[i];
                   return -1;
                 }


                 /* Find priority of node with given id. Return -1 if not found. */
                 int getPriority(id)
             #ifdef PTR_TO_PROC_TABLE_MODE
                 struct proc *id;
             #else
                 int id;
             #endif
                 {
                   int i;
                   for (i=0; i < heapsize; i++) 
                     if (id == id_array[i]) return priority_array[i];
                   return -1;
                 }


                 /* Set the priority of a node. Return 0 if successful, else -1. */
                 int setPriority(id, priority)
             #ifdef PTR_TO_PROC_TABLE_MODE
                 struct proc *id;
             #else 
                 int id;
             #endif
                 int priority;
                 {
                   int i, hold_heapsize;
                   i = 0;
                   while (i < heapsize)
                   {
                     if (id == id_array[i]) {
                       priority_array[i] = priority;
                       hold_heapsize = heapsize;
                       for (heapsize = 2; heapsize <= hold_heapsize; heapsize++) {
                         heapifyUp();
             #ifdef DEBUG_OUTSIDE_OF_MINIX
                         showHeap('^');
             #endif
                       }
                       heapsize = hold_heapsize;
                       return 0; 
                     }
                     i++;
                   }
                   return -1;
                 }


             /* Increase priorities of all nodes by some amount */
             void bumpAllPriorities(amount)
             int amount;
             {
               int i;
               for (i=0; i < heapsize; i++) priority_array[i] += amount;
             }


             #ifdef INCLUDE_HEAP_TEST_CODE
                 void main()
                 {
                   insertIntoHeap(1,13);
                   insertIntoHeap(2,22);
                   insertIntoHeap(3,45);
                   insertIntoHeap(4,81);
                   insertIntoHeap(5,13);
                   insertIntoHeap(6,22);
                   insertIntoHeap(7,13);
                   insertIntoHeap(8,45);
                   insertIntoHeap(9,81);
             #ifdef DEBUG_OUTSIDE_OF_MINIX
                   showHeap('*');
             #endif
                   setPriority(4,13);
                   setPriority(10,10);
             #ifdef DEBUG_OUTSIDE_OF_MINIX
                   showHeap('*');
             #endif
                   printf("%d\n", extractFromTopOfHeap());
                   printf("%d\n", extractFromTopOfHeap());
                   printf("%d\n", extractFromTopOfHeap());
                   printf("%d\n", extractFromTopOfHeap());
             #ifdef DEBUG_OUTSIDE_OF_MINIX
                   printf("Wait count for %d is %d.\n", 7, getWaitCount(7));
                   printf("Wait count for %d is %d.\n", 10, getWaitCount(10));
             #endif
                   printf("%d\n", extractFromTopOfHeap());
                   printf("%d\n", extractFromTopOfHeap());
                   printf("%d\n", extractFromTopOfHeap());
                   printf("%d\n", extractFromTopOfHeap());
                   printf("%d\n", extractFromTopOfHeap());
                   printf("%d\n", extractFromTopOfHeap());
                   printf("\n");
                 }
             #endif