# 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 <= 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++) {
}
}

-
typedef const char Datatyp; Datatyp... is that a typo, or something you can't change? –  Corbin Feb 12 at 21:17
Something I can't change. I can't see any reason for having it. My teachers word is my law. –  Emz Feb 12 at 21:20
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. –  Roger Feb 12 at 21:27
Tell me about it, if I could change them, I would. Wasn't easy finding material on the topic because of this standard. –  Emz Feb 12 at 21:49
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... –  Lundin Feb 13 at 8:50

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


• 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)
}

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

-
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 Feb 12 at 23:39
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. –  Emz Feb 12 at 23:43
@Emz I updated my answer with various options for a return code, and some test results. –  ChrisW Feb 12 at 23:55
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 Feb 13 at 9:41
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 –  Emz Feb 13 at 10:05