cpointersqueueinsertion-sortcircular-queue

In a circular queue how to check if the iterator is greater than and equal to the front element of the queue


struct PCB
{
    int PID;
    int burstTime;
    int arrivalTime;
    int priorityScore;
    int startTime;
    int finishTime;
};

struct Queue
{
    int front;
    int rear;
    int length;       // Stores the maximum no. of processes that can be stored processes in the queue
    int size;         // Stores the current no. of processes in the queue
    struct PCB **arr; // Array of pointers storing the pointers to PCB. Storing "struct PCB*" type item in arr
};

void arrangeProcess(struct Queue *readyQ)
{
    if (isEmpty(readyQ))
    {
        printf("\nNo elements in Queue.\n");
        return;
    }

    int i = readyQ->front, temp = readyQ->size;
    int j, tempj;
    struct PCB *key;

    i = (i + 1) % readyQ->length;

    while (i < temp)
    {
        key = readyQ->arr[i];
        j = (i + (readyQ->length) - 1) % readyQ->length; // Getting the previous element of i

        int lastIndex = (readyQ->front + readyQ->length - 1) % readyQ->length;

        // The while loop is executed if (j >= readyQ->front) and AT of arr[j] > AT of key
        while ((j != lastIndex) && ((readyQ->arr[j]->arrivalTime) > (key->arrivalTime))) 
        {
            tempj = (j + 1) % readyQ->length; // Getting the next element of j

            readyQ->arr[tempj] = readyQ->arr[j];

            j = (j + (readyQ->length) - 1) % readyQ->length;
        }
        tempj = (j + 1) % readyQ->length;
        readyQ->arr[tempj] = key;

        i = (i + 1) % readyQ->length;
    }
}

The main object here is to sort the PCBs in the readyQ according to the Arrival time which I am trying to do using insertion sort but I cannot find a suitable condition for the inner loop of insertion sort to run for the queue till the iterator i greater than and equal to the front element of the readyQ. The condition I have written in the program is going on loop if readyQ is full i.e. when the last element is present in the readyQ otherwise it is running perfectly.

Please suggest the suitable loop condition so that the code runs perfectly even in case last element is present in the readyQ


Solution

  • Don't work with the actual offsets. Write the loops in terms of 0..size-1, but actually compare elements (front + i) % length and (front + j) % length

    void arrangeProcess(struct Queue *readyQ)
    {
        size_t num_eles = readyQ->size;
        if (!num_eles)
            return;
    
        size_t base_idx = readyQ->front;
        size_t max_eles = readyQ->length;
    
        for (size_t i=0; i<num_eles-1; ++i) {
            size_t ii = ( base_idx + i ) % max_eles;
            struct PCB *a = readyQ->arr[ii];
    
            for (size_t j=i+1; j<num_eles; ++j) {
                size_t jj = ( base_idx + j ) % max_eles;
                struct PCB *b = readyQ->arr[jj];
    
                ...
            }
        }
    }
    

    It's a lot simpler and less error prone.