Optimization for add function in queue

I would prefer if more experienced users could give pointers on how I can optimize and think better when writing code.

Using Homework Questions as reference, as this is a homework related question. This should fall into the second category. I know the code is working and that no memory is leaking. The implementation nor the queue.h can not be changed.

queue.h:

#define MAX_PRIO 100
typedef const char Datatyp;

#ifndef QUEUE_H
#define QUEUE_H

struct Qelement {                           // type of a queue
    struct Qelement *next;                  // pointer to next element
    int prio;                               // order in queue
    Datatyp *dataptr;                       // pointer to data
}; 

typedef struct Qelement *Queue;

queue.c: (This is were feedback is wanted)

// creating an empty queue
Queue new_queue ()
{
    Queue q = (Queue)malloc(sizeof(struct Qelement));
    q->next = NULL;
    q->prio = MAX_PRIO;
    q->dataptr = NULL;  
    return q;
}

// adding a new element to queue based on priority
// higher priority means earlier in queue
void add (Queue q, int priority, Datatyp *d)
{
    // initiation
    Queue previous = q;
    Queue element = (Queue)malloc (sizeof(struct Qelement));
    Queue tmp = NULL;

    while (priority prio)
    {
        if (previous->next != NULL)
        {
            tmp = previous;
            previous = previous->next;
        }
        else if (tmp != NULL)
        {
            tmp = previous;
            previous = previous->next;
            break;
        }
        else
        {
            break;
        }       
    }

    element->prio = priority;
    element->dataptr = d;

    if (tmp == NULL)
    {
        element->next = NULL;
        previous->next = element;
    }
    else
    {
        element->next = previous;
        tmp->next = element;
    }
}

The code is then used along these lines. (This part can not be changed)

```
int main () {
const char *daniel = "Daniel";
const

-
Your variable's names confused me; I'd suggest renaming 'previous' to 'current', and 'tmp' to 'previous'.

-
You don't do anything sensible if malloc fails.

-
The following ...

else if (tmp != NULL)
{
    tmp = previous;
    previous = previous->next;
    break;
}
else
{
    break;
}

... could be rewritten as ...

else
{
    if (tmp != NULL)
    {
        tmp = previous;
        previous = NULL;
    }
    break;
}

-
IMO you should ignore the alleged priority assigned to the head q element (because you never want to put anything in front of it).

1st version

In summary you could rewrite it to be something like this:

bool add (Queue q, int priority, Datatyp *d)
{
    // initiation
    Queue element = (Queue)malloc (sizeof(struct Qelement));
    if (element == NULL)
        return false;
    element->prio = priority;
    element->dataptr = d;

    // loop until end of list or higher priority than next item
    for (; (q->next != NULL) && (q->next->prio >= priority); q = q->next)
    { } // an empty statement

    // insert element
    element->next = q->next;
    q->next = element;
    return true;
}

Advantages of this version over your implementation:

• No danger of adding in front of the first, passed-in q element, even if the passed-in priority is greater than MAX_PRIO

• No extra local variables (you have 2: tmp and previous)

• No if or else statements (you have 5)

• It's obvious what the algorithm is (search the list after the first node until you find the right spot, then insert into the list there)

2nd version

It's not clear whether your Queue new_queue() is part of the code which we're allowed to review.

Assuming that we are allowed to review/change that, I would add, "**Don't create "first element" which represents (contains a first pointer to) the queue: instead the queue should be represented by a pointer to the first real element."

Your first node (allocated using new_queue) might be what's called a "sentinel node" (see references here and here). It's also possible to create a queue without using a sentinel node: the "queue" is simply a pointer to the first node (instead of being a pointer to a node which contains a pointer to the first real node).

void add (Queue* qptr, int priority, Datatyp *d)
{
    // initiation
    Queue element = (Queue)malloc (sizeof(struct Qelement));
    element->prio = priority;
    element->dataptr = d;

    // get first element of queue
    Queue q = *qptr;
    if ((q == NULL) // queue was empty
        || (priority > q->prio)) // higher priority than first queue item
    {
        // insert at front of queue
        element->next = q;
        // caller's qptr now points to the new first node
        *qptr = element;
        return;
    }

    // else insert later in the queue using the same code as above    
    for (; (q->next != NULL) && (q->next->prio >= priority); q = q->next)
    { }

    // insert element
    element->next = q->next;
    q->next = element;
}

... used like this ...

int main () {
    const char *daniel = "Daniel";
    const char *lisa = "Lisa";
    const char *a[] = {"Kalle", "Olle", "Eva", lisa, "Stina", 
                      "Peter", "Anna", daniel, "Johan", "Maria"};

    // not q = new_queue()
    // instead let q be pointer to first real node
    // and q is null represent an empty list
    Queue q = NULL;

    for (int i=0; i<10; i++) {
        // pass Queue* qptr = &q (address of queue)
        // so that add can modify the value contained in q
        // (i.e. modify the node to which q is pointing)
        add(&q, i%4, a[i]); 
    }

    // q is now a pointer to the first element
}

Sadly, I can not change add to be a bool either. Is there any other way of handling it (except of very obscured ones) without changing add to a bool?

Some C conventions are:

• return int (often 0 for success and -1 for failure)

• return something useful like 'Queue' (the most recently-added element) or 0 (if a new element couldn't be created

• throw an exception (if it's C++)

• Include `






• Ignore the fact that malloc` might fail.

Tell me about it, that is how I did it at first, and it turned out that the main function gave me a billion errors because apparently the first element of the queue should only be a pointer to the first real element.

I tested the above code by adding the following statement to the end of main:

// q is now a pointer to the first element

for (;q;q=q->next)
{
    printf(q->dataptr);
    printf("\r\n");
}

It generated the following output (which I think is correct):

Lisa
Daniel
Eva
Anna
Olle
Peter
Maria
Kalle
Stina
Johan

StackExchange Code Review Q#41504, answer score: 5