trjhtr

This is from an exercise I've done:

We want to implement a priority queue system to plan the execution of the system processes. An array of MAXPRI represents the priorities of the system, where 0 is the highest priority and MAXPRI-1 is the lowest priority. Each position i in the array will contain a dynamic linked list where the first element of this is the priority i process that must be executed (provided there are no processes available in the previous i-1 positions). Implement the following operations:

Create. Initialize array.

AddProcess. Given a priority and a process identifier, it adds the process to the end of the corresponding list.

ExecuteProcess. Remove from the list the most priority process. If there are no processes to execute, it will be indicated with a warning message.

Search. Given a process identifier it returns the priority of this one. If the id of the process does not exist, -1 will be returned.

Display. Go through the structure to show the existing processes that are available for execution sorted by priority (highest first).

main.c, linkedListArray.c, linkedListArray.h

#include "linkedListArray.h"

void Create(Node **queue)

 for (int i = 0; i < MAXPRI; i++) 
 queue[i] = NULL;
 


void Push(Node **queue, int pri, int id)

 Node *new_node = malloc(sizeof(Node));
 if (new_node != NULL) 
 new_node->id = id;
 new_node->next = NULL;
 if (queue[pri] == NULL) 
 queue[pri] = new_node;
 
 else 
 Node *aux = queue[pri];
 while (aux->next != NULL) 
 aux = aux->next;
 
 aux->next = new_node;
 
 


void Execute(Node **queue)

 bool end = false;
 int i = 0;

 while (!end && i < MAXPRI) 
 if (queue[i] != NULL) 
 Node *aux = queue[i];
 queue[i] = queue[i]->next;
 free(aux);
 end = true;
 
 i++;
 
 if (!end) 
 printf("There are no processesn");
 


int Search(Node **queue, unsigned int id)

 int pri = -1;
 Node *aux;

 for (int i = 0; i < MAXPRI && pri == -1; ++i) 
 aux = queue[i];
 while (aux != NULL && pri == -1) 
 if (aux->id == id) 
 pri = i;
 
 else
 aux = aux->next;
 
 
 return pri;


void Output(Node *head)

 for (Node *current = head; current != NULL; current = current->next) 
 if (current->next != NULL)
 printf ("%d -> ", current->id);
 else
 printf ("%d", current->id);
 


void Display(Node **queue)

 for (int i = 0; i < MAXPRI; i++) 
 printf ("Priority queue %d: ", i);
 Output(queue[i]);
 putchar('n');
 
 putchar('n');

• 
  

  An if clause of Output is only executed once, on the very first node. You may avoid this logic altogether by making it explicit:

  
  
  

  if (!head)
   return;
  printf("%d", head->id);
  
  for (head = head->next; head; head = head->next) 
   printf(" -> %d", head->id);
  
  

  
  
  

  A missing

  
  
  

  printf("n");
  

  
  
  

  seems like a bug (I hope it is a copy-paste error).

  
  


• 
  

  An early return helps to avoid unnecessary variables. Consider Search:

  
  
  

  for (int i = 0; i < MAXPRI; i++)
   for (Node * aux = queue[i]; aux; aux = aux->next) 
   if (aux->id == id) 
   return i;
   
   
  }
  return -1;
  

  
  
  

  A perk benefit is that now you can rename meaningless i to a more reasonable pri.

  
  
  

  Similarly, if Execute returns as soon as a process is found, you wouldn't need bool end.

  
  


• 
  

  I strongly recommend to factor the

  
  
  

   while (aux->next != NULL) 
   aux = aux->next;
   
  

  
  
  

  loop into a function (say, get_tail), and streamline Push:

  
  
  

  Node * node = new_node(id);
  Node * tail = get_tail(pri);
  if (tail) 
   tail->next = node;
   else 
   queue[pri] = node;
  
  

  
  


• 
  

  Using extra memory may significantly reduce the run time. In your case, the

  
  
  

  struct list 
   Node * head;
   Node * tail;
  ;
  

  
  
  

  would reduce looking for tail complexity from linear to $O(1)$.

  
  



• linkedListArray.h shall only export the names defined in linkedListArray.c. The #include files required for linkedListArray.c compilation should be included directly in linkedListArray.c.