Optimization for add function in queue

Question

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 <= previous->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 char *lisa = "Lisa";
 const char *a[] = {"Kalle", "Olle", "Eva", lisa, "Stina", 
 "Peter", "Anna", daniel, "Johan", "Maria"};
 Queue q = new_queue();
 int i;
 for (i=0; i<10; i++) {
 add(q, i%4, a[i]); 
 }
}

• Corbin: typedef const char Datatyp; Datatyp... is that a typo, or something you can't change?
• Emz: Something I can't change. I can't see any reason for having it. My teachers word is my law.
• Roger: Just a tiny note -- by convention, the method to add items to a queue is typically called enqueue and to remove is called dequeue. These are analogous to the push and pop conventions of a stack.
• Emz: Tell me about it, if I could change them, I would. Wasn't easy finding material on the topic because of this standard.
• Lundin: typedef struct Qelement *Queue; To hide a pointer behind a typedef is considered very bad practice, because it makes the program bug-prone and hard to read. If this comes from your teacher, be aware that they are teaching you bad programming practice...

Answer 1

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

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

3. 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;
   }
   

4. 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 <stdbool.h>
• 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

• Emz: I will be trying this tomorrow. 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? I almost want to show the teacher your first comment.
• Emz: 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. My getFirstelement function is sexy... return q->next->next; regarding the add by reference part, I was told that on numerous different places now... makes one wonder what I am being taught in school.
• ChrisW: @Emz I updated my answer with various options for a return code, and some test results.
• Emz: As I thought, I have to ignore it. Last question! Can you provide some reliable source which I can reference to when I talk to the teacher about the structure of how to implement a more standard queue? So the teacher might share that with the other students. I now know how it is supposed to be done, but the other students do not. Must just want to get done with the exercise and get on to the next.
• Emz: Rereading your code again I see you added "add at front" which according to the specifics of the exercise should never happen, as the first queue element is initialized with the MAX_PRIO