Queue in C

[pandit]

AIM: Just wanted to write a queue in C, to know C better.
PROBLEM: no problems in code
WHAT I WANT: want comments from CLC for better C coding,
program design etc.

its working on solorias 10 with gcc 3.4.6.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


struct node
{
char c;
struct node* next;
};


struct queue
{
struct node* head;
struct node* tail;
};


/* for every function 0 is returned for success and negative integer for
* failure. -11 is reserved for args check and -12 for malloc() failure */
int enqueue(struct queue* q, char cr);
void dequeue(struct queue* q, struct node* np);
void create_queue(struct queue** q);
void print_queue(struct queue* q);
void print_node(struct node p);


/* These operatiors was created just for the sake of understanding
* pointers.
*/
int search_queue(struct queue* q, const char cr);
int delete_from_queue(struct queue* q, const char cr);
int insert_after(struct queue* q, const char cr, const char elem);
int insert_before(struct queue* q, const char cr, const char elem);



int main(void)
{
int i, r;
struct queue* q;
struct node p;

create_queue(&q);
for(i = 97; i <= 101; ++i)
{
if((r = enqueue(q, i))) /* implicit conversion to charcter intended */
{
printf("Could not enqueue, r = %d\n", r);
}
}

print_queue(q);
dequeue(q, &p);
print_queue(q);
print_node(p);
printf("Element 'n' exist == %d\n\n", search_queue(q, 'n'));
delete_from_queue(q, 'e');
print_queue(q);
delete_from_queue(q, 'b');
print_queue(q);

printf("Element 'd' exist == %d\n\n", search_queue(q, 'd'));

insert_after(q, 'e', 'd');
insert_after(q, 's', 'r');
print_queue(q);
insert_before(q, 'b', 'c');
insert_before(q, 'a', 'b');
insert_before(q, 'a', 'B');
print_queue(q);

return EXIT_SUCCESS;
}



/* insert "cr" before "elem" */
int insert_before(struct queue* q, const char cr, const char elem)
{
struct node *prev, *temp;
if((NULL == q) || (NULL == q->head)) return -11;

for(prev = NULL, temp = q->head; temp; temp = temp->next)
{
if(elem == temp->c)
{
struct node* t = malloc(1 * (sizeof *t));
if(NULL == t) return -12;
t->c = cr;
if(NULL == prev) /* we are dealing with head */
{
t->next = q->head;
q->head = t;
}
else
{
prev->next = t;
t->next = temp;
}
return 0;
}
else
{
prev = temp;
}
}

return -13;
}


/* insert "cr" next to "elem" */
int insert_after(struct queue* q, const char cr, const char elem)
{
struct node* temp;
if((NULL == q) || (NULL == q->head)) return -11;

for(temp = q->head; temp; temp = temp->next)
{
if(elem == temp->c)
{
struct node* t = malloc(1 * (sizeof *t));
if(NULL == t) return -12;
t->c = cr;
t->next = temp->next;
temp->next = t;
return 0;
}
}

return -13;
}


int search_queue(struct queue* q, const char cr)
{
struct node* temp;
if((NULL == q) || (NULL == q->head)) return -11;

for(temp = q->head; temp; temp = temp->next)
{
if((cr == temp->c)) return 0;
}

return -13;
}


int delete_from_queue(struct queue* q, const char cr)
{
struct node *prev, *temp;;
if((NULL == q) || (NULL == q->head)) return -11;

for(prev = NULL, temp = q->head; temp; temp = temp->next)
{
if(cr == temp->c)
{
if(NULL == prev) /* we are dealing with head */
{
q->head = temp->next;
free(temp);
if(NULL == q->head) q->tail = q->head;
return 0;
}
else
{
prev->next = temp->next ;
free(temp);
if(NULL == prev->next) q->tail = prev->next;
return 0;
}
}
else
{
prev = temp;
}
}

return -13;
}


int enqueue(struct queue* q, char cr)
{
struct node* p;
if((NULL == q)) return -11;

p = malloc(1 * (sizeof *p));
if(NULL == p) return -12;
else p->c = cr;

if((NULL == q->head) && (NULL == q->tail))
{
q->head = q->tail = p;
}
else if((NULL == q->head) || (NULL == q->tail))
{
free(p);
return -13;
}
else
{
struct node* temp = q->tail;
temp->next = p;
q->tail = p;
}

return 0;
}


void dequeue(struct queue* q, struct node* np)
{
struct node* temp;

if((NULL == q) || (NULL == np)) return;
if((NULL == q->tail)) return;

temp = q->head;
q->head = q->head->next;
np->c = temp->c;
free(temp);
if(NULL == q->head) q->tail = q->head;
}


void print_queue(struct queue* q)
{
if(q)
{
struct node* temp = q->head;
while(temp)
{
printf("Element = %c\n", temp->c);
temp = temp->next;
}
printf("--------------- EoQ -----------\n\n");
}
}

void print_node(struct node p)
{
printf("Node = %c\n", p.c);
}

void create_queue(struct queue** q)
{
if(q && *q)
{
*q = malloc(1 * (sizeof **q));
if(NULL == *q) exit(EXIT_FAILURE);

(*q)->head = (*q)->tail = NULL;
}
}



================ OUTPUT ====================
$ gcc -ansi -pedantic -Wall -Wextra LL.c
$ ./a.out
Element = a
Element = b
Element = c
Element = d
Element = e
--------------- EoQ -----------

Element = b
Element = c
Element = d
Element = e
--------------- EoQ -----------

Node = a
Element 'n' exist == -13

Element = b
Element = c
Element = d
--------------- EoQ -----------

Element = c
Element = d
--------------- EoQ -----------

Element 'd' exist == 0

Element = c
Element = d
Element = e
--------------- EoQ -----------

Element = a
Element = b
Element = c
Element = d
Element = e
--------------- EoQ -----------

 

[Ike Naar]

int main(void)
{
int i, r;
struct queue* q;

q is not initialized so its value is indeterminate.

struct node p;

create_queue(&q);

create_queue is called with &q as its argument.

Looking at the definition of create_queue:

void create_queue(struct queue** q)
{
if(q && *q)

In the call from main(), *q is indeterminate.
If it happens to be a null pointer, then the body of
the if statement is not executed and no queue will be
created.
What is the reason for testing the value of *q in the
if condition anyway?

 

[Ike Naar]

int delete_from_queue(struct queue* q, const char cr)
{
struct node *prev, *temp;;
if((NULL == q) || (NULL == q->head)) return -11;

for(prev = NULL, temp = q->head; temp; temp = temp->next)
{
if(cr == temp->c)
{
if(NULL == prev) /* we are dealing with head */
{
q->head = temp->next;
free(temp);
if(NULL == q->head) q->tail = q->head;
return 0;
}
else
{
prev->next = temp->next ;
free(temp);
if(NULL == prev->next) q->tail = prev->next;

Here you set q->tail to NULL which is not correct.
For a nonempty queue, q->tail should point to the last
node in the queue, which is 'prev' at this point.

 

[Ike Naar]

int insert_after(struct queue* q, const char cr, const char elem)
{
struct node* temp;
if((NULL == q) || (NULL == q->head)) return -11;

for(temp = q->head; temp; temp = temp->next)
{
if(elem == temp->c)
{
struct node* t = malloc(1 * (sizeof *t));
if(NULL == t) return -12;
t->c = cr;
t->next = temp->next;
temp->next = t;

If t is the last node in the list, q->tail should be updated:

if (t->next == 0) q->tail = t;

 

[Malcolm McLean]

AIM: Just wanted to write a queue in C, to know C better.

PROBLEM: no problems in code

WHAT I WANT: want comments from CLC for better C coding,
program design etc.

You can either implement a queue as a linked list, or as circular
buffer. The linked list is a bit easier to write, and is naturally
unbounded. The circular buffer will normally execute faster,
but it's slightly tricky to ensure the head and tail positions
don't overlap and wrap correctly. Also if the queue becomes too long
for the buffer, you have problems.

 

[BartC]

WHAT I WANT: want comments from CLC for better C coding,
program design etc.

return -13;

return -13;

return -13;
return -13;

return -13;

It's not clear what all these -13s mean.

Presumably they are an error return (but code -13 not documented). You
should use a #define or enum name for these:

#define unknownerror -13

.....

return unknownerror;

But using a more descriptive name for whatever this error actually is.

 

[Barry Schwarz]

AIM: Just wanted to write a queue in C, to know C better.
PROBLEM: no problems in code
WHAT I WANT: want comments from CLC for better C coding,
program design etc.

its working on solorias 10 with gcc 3.4.6.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


struct node
{
char c;
struct node* next;
};


struct queue
{
struct node* head;
struct node* tail;
};


/* for every function 0 is returned for success and negative integer for
* failure. -11 is reserved for args check and -12 for malloc() failure */

True for only five functions and partially true for main. None of the
others return an int.

int enqueue(struct queue* q, char cr);

I wonder why cr is not const like it is in the last four prototypes
below.

void dequeue(struct queue* q, struct node* np);
void create_queue(struct queue** q);
void print_queue(struct queue* q);
void print_node(struct node p);


/* These operatiors was created just for the sake of understanding
* pointers.
*/
int search_queue(struct queue* q, const char cr);
int delete_from_queue(struct queue* q, const char cr);
int insert_after(struct queue* q, const char cr, const char elem);
int insert_before(struct queue* q, const char cr, const char elem);



int main(void)
{
int i, r;
struct queue* q;
struct node p;

create_queue(&q);
for(i = 97; i <= 101; ++i)

Why use magic numbers that are meaningless on some machines. You
could just as easily (and more understandably) code
for (i = 'a'; i <= 'e'; ++i)
which will work for both ASCII and EBCDIC.

{
if((r = enqueue(q, i))) /* implicit conversion to charcter intended */
{
printf("Could not enqueue, r = %d\n", r);

Wouldn't it would be useful to tell the user which value of i failed?

}
}

print_queue(q);
dequeue(q, &p);
print_queue(q);
print_node(p);
printf("Element 'n' exist == %d\n\n", search_queue(q, 'n'));
delete_from_queue(q, 'e');

101 is not 'e' on my machine.

print_queue(q);
delete_from_queue(q, 'b');
print_queue(q);

printf("Element 'd' exist == %d\n\n", search_queue(q, 'd'));

insert_after(q, 'e', 'd');
insert_after(q, 's', 'r');
print_queue(q);
insert_before(q, 'b', 'c');
insert_before(q, 'a', 'b');
insert_before(q, 'a', 'B');
print_queue(q);

return EXIT_SUCCESS;
}

void create_queue(struct queue** q)
{
if(q && *q)
{
*q = malloc(1 * (sizeof **q));
if(NULL == *q) exit(EXIT_FAILURE);

Wouldn't it be nice to tell the user why you are aborting the program?

 

[Barry Schwarz]

int enqueue(struct queue* q, char cr)
{
struct node* p;
if((NULL == q)) return -11;

p = malloc(1 * (sizeof *p));
if(NULL == p) return -12;
else p->c = cr;

if((NULL == q->head) && (NULL == q->tail))

If q->head is NULL, can q->tail be anything else? Why check both?

{
q->head = q->tail = p;
}
else if((NULL == q->head) || (NULL == q->tail))

When can this ever evaluate to true?

{
free(p);
return -13;
}
else
{
struct node* temp = q->tail;
temp->next = p;

temp serves no purpose. This is equivalent to
q->tail->next = p;

 

[Barry Schwarz]

void print_node(struct node p)

It is not a big deal since struct node is small but it is much more
common to pass a pointer to struct rather than an actual struct.

 

[Stefan Ram]

void create_queue(struct queue** q)
{
if(q && *q)
{
*q = malloc(1 * (sizeof **q));
if(NULL == *q) exit(EXIT_FAILURE);

My personal coding style does not permit a library function
to terminate an application. So, I'd write something like:

void init_queue( struct queue * const q ){ q->head = q->tail = 0; }

struct queue * new_queue()
{ struct queue * const q = malloc( sizeof *q );
if( q )init_queue( q );
return q; }

struct queue * create_queue( struct queue * * const q )
{ return *q = new_queue(); }

(untested)

 

[Malcolm McLean]

My personal coding style does not permit a library function
to terminate an application. So, I'd write something like:

In Baby X, I do all memory allocation via bbx_malloc(), which never returns null.
That's so that the user doesn't have to check almost every single Baby X call for
allocation failure. In xlib, you're not guaranteed clean behaviour if the X server
runs out of memory, so we're not losing anything theoretically.

Of course it's impossible to guarantee that box_malloc() will always give you the
memory you ask for. So currently it calls exit() if it can't allocate memory.
At some point I'll replace that with a user message. but the problem is that the user
message itself requires memory.

 

[Keith Thompson]

/* for every function 0 is returned for success and negative integer for
* failure. -11 is reserved for args check and -12 for malloc() failure */
[...]

for(i = 97; i <= 101; ++i)
{
if((r = enqueue(q, i))) /* implicit conversion to charcter intended */
{
printf("Could not enqueue, r = %d\n", r);
}
}

What is the significance of the numbers 97 and 101? If they're supposed
to be 'a' and 'e', then write 'a' and 'e'. (Strictly speaking, there's
no guarantee in the language that the values of 'a' through 'e' are
contiguous, but it turns out to be a reasonably safe assumption, even
for EBCDIC systems.)

Various functions return -11, -12, and -13 in various circumstances.
You never said what -13 means -- and you shouldn't expect users the
values to be obvious just becuase you mentioned them in a comment.
Reserving specific values for error codes is great, but define them as
named constants.

http://en.wikipedia.org/wiki/Magic_number_(programming)#Unnamed_numerical_constants

 

[Malcolm McLean]

Reserving specific values for error codes is great, but define them as
named constants.

Consider this.

Our program makes use of a small but still reasonably large number of file formats, for
various this around the program. For example it uses JPEG, GIF, BMP and PNG formats to store
images, xml for configuration, a vector format for vector graphics, and internal format
for save states.
Now there are essentially three things that can happen when we try to load or save a file.
The function can work correctly, the user can pass a path which doesn't exist or is
illegal, there can be an IO error, there can be a parse error (file or data in a format the
function cannot read), or the computer can run out of memory. That's about it.

So let's say we define

#define ERR_OUT_OF_MEMORY -1

Then we put that definition in jpeg.h. Great, but then xml.h has to include jpeg.h. Not
acceptable. So maybe put the definition in file_errors.h Better, but now jpeg.c and jpeg.h
are not idempotent. Not good.
OK, so make in JPEG_ERR_OUT_OF_MEMORY.
Well OK. Better. But we've obscured the fact that all the errors are essentially the same.
JPEG_OUT_OF_MEMORY = PNG_OUT_OF_MEMORY = XML_OUT_OF_MEMORY. It's all the
same underlying problem.

Or use the convention that -1 always indicates an out-of-memory error.

Much better, except that the convention isn't established. So establish it locally.

 

[Martin Shobe]

Consider this.

Our program makes use of a small but still reasonably large number of file formats, for
various this around the program. For example it uses JPEG, GIF, BMP and PNG formats to store
images, xml for configuration, a vector format for vector graphics, and internal format
for save states.
Now there are essentially three things that can happen when we try to load or save a file.
The function can work correctly, the user can pass a path which doesn't exist or is
illegal, there can be an IO error, there can be a parse error (file or data in a format the
function cannot read), or the computer can run out of memory. That's about it.

So let's say we define

#define ERR_OUT_OF_MEMORY -1

Then we put that definition in jpeg.h. Great, but then xml.h has to include jpeg.h. Not
acceptable. So maybe put the definition in file_errors.h Better, but now jpeg.c and jpeg.h
are not idempotent. Not good.

Why couldn't you put the define in file_errors.h and make jpeg.h and
jpeg.c idempotent? (Though I don't see why we would should care if
jpeg.c is idempotent.) It's what I do in situations like that.

Martin Shobe

 

[Keith Thompson]

It's not clear what all these -13s mean.

Presumably they are an error return (but code -13 not documented). You
should use a #define or enum name for these:

#define unknownerror -13

[...]

That should be

#define unknownerror (-13)

to avoid operator precedence problems. It's likely that there are no
actual uses of unknownerror that would cause problems, but it's better
to be safe.

And it's conventional to use all-caps for macro names; I suggest
following that convention unless you have a good reason not to.

 

[Keith Thompson]

[...]

int enqueue(struct queue* q, char cr);

I wonder why cr is not const like it is in the last four prototypes
below. [...]

/* These operatiors was created just for the sake of understanding
* pointers.
*/
int search_queue(struct queue* q, const char cr);
int delete_from_queue(struct queue* q, const char cr);
int insert_after(struct queue* q, const char cr, const char elem);
int insert_before(struct queue* q, const char cr, const char elem);

I wonder why cr *is* const in those last four prototypes. The "const"
has no meaning for callers; it only prevents any modifications to cr
inside the function.

It would be reasonable to have "const char cr" in the function
definition and just "char cr" in the separate prototype. (Or you could
just use "char cr" everywhere, which is perhaps mildly sloppy but common
practice.)

[...]

Why use magic numbers that are meaningless on some machines. You
could just as easily (and more understandably) code
for (i = 'a'; i <= 'e'; ++i)
which will work for both ASCII and EBCDIC.

To expand on that: the C standard makes no guarantees about the numeric
values of 'a' through 'z' or 'A' through 'Z'. In particular, it doesn't
guarantee that their values are contiguous.

In the ASCII and ASCII-derived character sets used by most modern
systems (including Unicode), the 26 lowercase letters *are* contiguous,
as are the 26 uppercase letters.

In EBCDIC, most commonly used on IBM mainframes, the letters are not
contiguous, but certain subranges are: 'a'..'i', 'j'..'r', and 's'..'z'
(and likewise for uppercase).

The letters 'a'..'e' are contiguous on every system I've ever heard of,
but the C standard doesn't guarantee that.

(It does guarantee that '0'..'9' are contiguous.)

101 is not 'e' on my machine.

You use EBCDIC?

[...]

 

[Keith Thompson]

[...]

if((NULL == q->head) && (NULL == q->tail))

If q->head is NULL, can q->tail be anything else? Why check both?

{
q->head = q->tail = p;
}
else if((NULL == q->head) || (NULL == q->tail))

When can this ever evaluate to true?

Perhaps when there's a bug in the code? An assert() might be a
good way to check that.

 

[Malcolm McLean]

On 5/19/2014 10:03 AM, Malcolm McLean wrote:

Why couldn't you put the define in file_errors.h and make jpeg.h and
jpeg.c idempotent? (Though I don't see why we would should care if
jpeg.c is idempotent.) It's what I do in situations like that.

You want to be able to take jpeg.c and drop in into anything that needs to read or
write jpegs. You don't want to be bothered messing about with an external file
for a few trivial errors.

 

[Ian Collins]

It's not clear what all these -13s mean.

Presumably they are an error return (but code -13 not documented). You
should use a #define or enum name for these:

#define unknownerror -13

[...]

That should be

#define unknownerror (-13)

to avoid operator precedence problems. It's likely that there are no
actual uses of unknownerror that would cause problems, but it's better
to be safe.

A good reason to use an enum for return values rather than an ugly macro.

And it's conventional to use all-caps for macro names; I suggest
following that convention unless you have a good reason not to.

Yet another...

 

[Ian Collins]

In Baby X, I do all memory allocation via bbx_malloc(), which never returns null.
That's so that the user doesn't have to check almost every single Baby X call for
allocation failure. In xlib, you're not guaranteed clean behaviour if the X server
runs out of memory, so we're not losing anything theoretically.

Of course it's impossible to guarantee that box_malloc() will always give you the
memory you ask for. So currently it calls exit() if it can't allocate memory.
At some point I'll replace that with a user message. but the problem is that the user
message itself requires memory.

Wouldn't an assertion be better than calling exit?