/*
           The following 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 affecting 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 below main() function (which is just test code) be included? */

             #define INCLUDE_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_IN_MINIX
*/         
  /* If so, should node identifiers really be pointers to proc structures? */
  /* In this case, "id" is misleading since it suggests an integer */ 
/*        
             #define PTR_TO_PROC_MODE
*/          

   /* Are we debugging in a stand alone environment? */

             #define DEBUG_OUTSIDE_MINIX


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

  /* 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
*/

   /* How big can the heap get? */ 
             #define MAX_NODES 1000


   /* Now begin generating code for the heap. */ 


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

             #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_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_IN_MINIX

  /* 
    Given pointer to proc structure, returns offset index to it in 
    the proc array. SHould be same as "nr" but I don't trust.  
  */      
             #ifdef PTR_TO_PROC_MODE 
                    int proc_index(p)
                    struct proc *p;
                    {
                      int i;
                      if (p == NIL_PROC) 
                      {
             #ifdef DEBUG_INSIDE_MINIX
                        kprintf("!");
             #endif
                        return -1;
                      }
                      for (i = 0; i < NR_PROCS; i++) 
                        if (p == pproc_addr[NR_TASKS+i]) 
                        {
             #ifdef DEBUG_INSIDE_MINIX
                          /* should never print these */ 
                          if (i != p->p_nr) kprintf("@");
                          if (proc_addr(i) != p) kprintf("&");
             #endif
                          return i;
                        }
             #ifdef DEBUG_INSIDE_MINIX
                      kprintf("?");
             #endif
                      return -1;
                    }    
             #endif  /* PTR_TO_PROC_MODE */ 
             #endif  /* USING_IN_MINIX */ 

             #ifndef USING_IN_MINIX 
             #ifdef  DEBUG_OUTSIDE_MINIX 
                 /* Display heap (for debugging outside Minix) */
                 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 
             #endif 

                 /* Switch two nodes in the heap */
                 void swapInHeap(i, j)
                 int i;
                 int j;
                 {
             #ifdef PTR_TO_PROC_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_MINIX
                       showHeap('.');
             #endif
                       }
                 }

                 /* Add a node to the heap if room for it. */
                 /* Return -1 if not. */ 
                 int insertIntoHeap(id, priority)
             #ifdef PTR_TO_PROC_MODE
                 struct proc *id;
             #else
                 int id;
             #endif
                 int priority;
                 {
                   if (heapsize >= MAX_NODES) return -1; 
                   id_array[heapsize] = id;
                   priority_array[heapsize] = priority;
                   wait_counter_array[heapsize++] = 0;
                   heapifyUp();
             #ifdef DEBUG_INSIDE_MINIX
                   kprintf("(+ %d %d)", heapsize, proc_index(id)); 
             #endif
             #ifdef DEBUG_OUTSIDE_MINIX
                       showHeap('^');
             #endif
                   return 0; 
                 }

                 /* 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_MINIX
                   showHeap('.');
             #endif
                   heapifyDown(bigger);
                   }
             #ifdef DEBUG_OUTSIDE_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_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_MODE
                 struct proc *extractFromTopOfHeap() 
             #else
                 int extractFromTopOfHeap() 
             #endif
                 {
                   int i;
             #ifdef PTR_TO_PROC_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_INSIDE_MINIX
                   kprintf("(^ %d %d)", heapsize, proc_index([id_array[heapsize])); 
             #endif
                   return id_array[heapsize];
                 }

   /* Delete specified node and reheapify. Return -1 if not found. */
                 int deleteFromHeap(id)
             #ifdef PTR_TO_PROC_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_INSIDE_MINIX
                   kprintf("(- %d %d)", heapsize, proc_index(id)); 
             #endif
                   return 0;
                 }

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

		/* rebuild whole heap from arrays */
                void rebuildHeap() 
                {
                   int hold_heapsize; 
                   hold_heapsize = heapsize;
                   for (heapsize = 2; heapsize <= hold_heapsize; heapsize++) 
                   {
                     heapifyUp();
             #ifdef DEBUG_OUTSIDE_MINIX
                     showHeap('^');
             #endif
                   }
                   heapsize = hold_heapsize;
                }

  /* Find wait count for node with given id. Return -1 if not found. */
                 int getWaitCount(id)
             #ifdef PTR_TO_PROC_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_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_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;
                       rebuildHeap(); 
                       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;
             }

             void promoteIdleNodes(delay, amount)
             int delay, amount; 
             {
                int i; 
                for (i=0; i < heapsize; i++) 
                  if (wait_counter_array[i] >= delay) 
                  {
                     priority_array[i] += amount;                      
                  } else { 
                     wait_counter_array[i]++; 
                  }                     
             }

             #ifndef USING_IN_MINIX 
             #ifdef  INCLUDE_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);
/*
                   insertIntoHeap(1,81);
                   insertIntoHeap(2,45);
                   insertIntoHeap(3,13);
                   insertIntoHeap(4,22);
                   insertIntoHeap(5,13);
                   insertIntoHeap(6,81);
                   insertIntoHeap(7,45);
                   insertIntoHeap(8,22);
                   insertIntoHeap(9,13);
*/
             #ifdef DEBUG_OUTSIDE_MINIX
                   showHeap('*');
             #endif
                   setPriority(4,13);
                   setPriority(10,10);
             #ifdef DEBUG_OUTSIDE_MINIX
                   showHeap('*');
             #endif
                   printf("%d\n", extractFromTopOfHeap());
                   printf("%d\n", extractFromTopOfHeap());
                   printf("%d\n", extractFromTopOfHeap());
                   printf("%d\n", extractFromTopOfHeap());
             #ifdef DEBUG_OUTSIDE_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   /* INCLUDE_TEST_CODE */ 
             #endif   /* USING_IN_MINIX */